寻求最优建筑翻新算法：相邻建筑至少翻新其一的最低成本问题

这个问题的核心是保证没有两栋相邻建筑都不翻新，我们可以用动态规划来跟踪两种状态的最小成本：

状态定义 #

我们定义两个状态变量（或数组）：

• skip[i]：处理到第i栋建筑（从0开始计数）时，第i栋不翻新，且前i+1栋完全满足条件的最小总成本
• take[i]：处理到第i栋建筑时，第i栋翻新，且前i+1栋完全满足条件的最小总成本

状态转移规则 #

1. 如果第i栋不翻新：那第i-1栋必须翻新（否则会出现相邻两栋都不翻新的违规情况），因此skip[i] = take[i-1]
2. 如果第i栋翻新：第i-1栋可以翻新也可以不翻新（两种情况都满足相邻约束），取两种状态里的最小成本加上当前建筑的翻新费用，即take[i] = min(skip[i-1], take[i-1]) + cost[i]

初始条件 #

针对第一栋建筑（索引0）：

• skip[0] = 0：不翻新它的成本为0（题目规定n≥2，后续相邻约束会修正单独不翻新的不合理情况）
• take[0] = cost[0]：翻新它的成本就是自身的翻新费用

计算示例（以题目给出的数组[50,30,40,60,10,30,10]为例） #

我们一步步计算每个状态：

• i=0：skip[0]=0，take[0]=50
• i=1：skip[1]=take[0]=50，take[1]=min(0,50)+30=30
• i=2：skip[2]=take[1]=30，take[2]=min(50,30)+40=70
• i=3：skip[3]=take[2]=70，take[3]=min(30,70)+60=90
• i=4：skip[4]=take[3]=90，take[4]=min(70,90)+10=80
• i=5：skip[5]=take[4]=80，take[5]=min(90,80)+30=110
• i=6：skip[6]=take[5]=110，take[6]=min(80,110)+10=90

最终的最小总成本是min(skip[6], take[6])=90，和题目示例的结果一致，对应翻新的是第2、3、5、7栋建筑（数组索引1、2、4、6）。

空间优化 #

因为每次计算只需要用到前一个状态的skip和take值，不需要保存整个数组，可以用两个变量代替，将空间复杂度从O(n)降到O(1)：

prev_skip = 0
prev_take = cost[0]

for i in range(1, len(cost)):
    curr_skip = prev_take
    curr_take = min(prev_skip, prev_take) + cost[i]
    prev_skip, prev_take = curr_skip, curr_take

min_total = min(prev_skip, prev_take)

内容的提问来源于stack exchange，提问作者jophny