剑指offer专项突击版第31天

剑指 Offer II 091. 粉刷房子

重新定义 c o s t s [ i ] [ j ] costs[i][j] costs[i][j] 为DP方程，表示为第 i i i 号房子粉刷成 j j j 色的最小的花费。

一个编程小技巧：与 j j j 不同的颜色可以用 ( j + 1 ) (j+1)%3 (j+1) 和 ( j + 2 ) (j+2)%3 (j+2) 表示。

class Solution {
public:
    const int INF = 0x3f3f3f3f;
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        for(int i = 1; i < costs.size(); i++ ) {
            int minn[3] = {INF,INF,INF};
            for(int j = 0; j < 3; j++) {
                minn[j] = min(costs[i-1][(j+1)%3],costs[i-1][(j+2)%3]);
            }
            for(int j = 0; j < 3; j++) {
                costs[i][j] += minn[j];
            }
        }
        int res = INF;
        for(int i = 0; i < 3; i++) {
            res = min(costs.back()[i],res);
        }
        return res;
    }
};
           

剑指 Offer II 092. 翻转字符

dp方程 d p = m i n ( d p + 1 , o n e ) dp = min(dp+1, one) dp=min(dp+1,one) ，dp表示 s [ i ] s[i] s[i] 以及之前的字符串，调整为单调递增的最小翻转次数， d p + 1 dp+1 dp+1 表示当前字符 0 0 0 翻转为 1 1 1， o n e one one 表示目前字符 1 1 1 的个数，同时也表示为将所有 1 1 1 翻转为 0 0 0 的次数。

总的来说翻转 d p dp dp 次会保证之前的字符串时单调递增的，就算最终包含 1 1 1 它也是放在 0 0 0 后面，所以只需考虑目前的字符 0 0 0 翻转成 1 1 1 的代价大 还是 将之前的所有 1 1 1 翻转成 0 0 0 的代价大。

class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int one = 0, dp = 0;
        for(int i = 0; i < s.size(); i++) {
            if(s[i] == '0') {
                dp = min(dp+1,one);
            } else {
                one++;
            }
        }
        return dp;
    }
};
           

剑指 Offer II 093. 最长斐波那契数列

待补题解