leetcode剑指 Offer II 091. 粉刷房子C++

链接: 剑指 Offer II 091. 粉刷房子

class Solution {
public:
    int minCost(vector>& costs) {
        vector dp(3);
        for(int i = 0;i<3;i++) dp[i]=costs[0][i];

        for(int i = 1;i
            vector newdp(3);
            for(int j = 0;j<3;j++)
                newdp[j] = min(dp[(j + 1) % 3], dp[(j + 2) % 3]) + costs[i][j];
            dp=newdp;
        }
        return *min_element(dp.begin(), dp.end());
    }
};

明确一些点：

1. 当我们遍历给定数组的一个节点时，即使这个节点的值是整个数组中最大的，那么选择这个点的时候，也可能是最小的
2. 当遍历到给定数组的一个节点时，如果选择这个节点时，那么它上一次需要选择的节点那么只有两个选择，（感觉类似 斐波那契额数列）