LC256.粉刷房子

题目

思路

• 不需要考虑从开始位置到当前位置的最小花销，状态难以确定。因为当前位置会影响下一个位置，就算当前位置取到了最优，那么如果综合了下一个位置去考虑，可能当前的选择就不是最优了。比如说，当前选了红色，发现开销最小，但是下一个位置可能也是红色，如果无法选取，那么整体来讲当前位置选红色并不是最好的。
• 如果当前位置确定了颜色，那么上一个位置的颜色一定也会被确定（不重复 + 开销小），顺序递推下去，就可以确定整体的序列。
• to_red表示[0, i - 1]序列当中，最后一个颜色选择红色，序列的整体最小开销。
• 当前颜色选择绿色的最小开销为costs[0][1] + min(to_red, to_blue)
• 关键在于确定状态转移方程的唯一性，不要出现前后干扰等情况。

代码

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int to_red = costs[0][0], to_blue = costs[0][1], to_green = costs[0][2];
        int n = costs.size();
        for (int i = 1; i < n; ++i) {
            int nxt_to_red = costs[i][0] + min(to_blue, to_green);
            int nxt_to_blue = costs[i][1] + min(to_red, to_green);
            int nxt_to_green = costs[i][2] + min(to_red, to_blue);
            to_red = nxt_to_red;
            to_blue = nxt_to_blue;
            to_green = nxt_to_green;
        }

        return min(to_red, min(to_blue, to_green));
    }
};