剑指offer专项突击版第31天

剑指 Offer II 091. 粉刷房子

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

一个编程小技巧：与 $j$ 不同的颜色可以用 $(j+1)$ 和 $(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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

剑指 Offer II 092. 翻转字符

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

总的来说翻转 $dp$ 次会保证之前的字符串时单调递增的，就算最终包含 $1$ 它也是放在 $0$ 后面，所以只需考虑目前的字符 $0$ 翻转成 $1$ 的代价大 还是 将之前的所有 $1$ 翻转成 $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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

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

待补题解