leetcode|动态规划

本文最后更新于:3 years ago

在搞懂动态规划之前,我们有必要提一下,记忆化搜索和动态规划的区别,我们以斐波拉契数列求第n项为例。

记忆化搜索 —— 自顶向下的解决问题

假设基本的问题已经解决了,在基本问题的基础上,解决现有问题。

例:假设 Fib(n - 1) 和 Fib(n - 2) 已解决,来解决 Fib(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
斐波拉契数列
O(n)
*/
long long Fib(int n, vector<long long> &a){ // 用 a 记录 Fib(1)、Fib(2)、Fib(3)...
if (n == 1 || n == 2) {
return 1;
}
if (a[n] == -1) {
a[n] = Fib(n - 1, a) + Fib(n - 2, a);
cout << n << endl;
}
return a[n];
}

int main(){
int n = 100;
vector<long long> a(n + 1, -1);
cout << Fib(n, a) << endl;
return 0;
}

动态规划 —— 自底而上的解决问题

先解决小数据量下的问题,再逐渐递增数据量。

例:先解决 Fib(3)、Fib(4) 等小数据量的问题,再递增到 Fib(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
斐波拉契数列
O(n)
*/
int main(){
int n = 100;
vector<long long> a(n, -1);
a[1] = 1;
a[2] = 1;
for (int i = 3; i <= n; i++) {
a[i] = a[i - 1] + a[i - 2];
}
cout << a[n] << endl;
return 0;
}

优化,因为只会用到 a[i - 1] 和 a[i - 2] 两个数,所以可以用滚动数组优化:

1
2
3
4
5
6
7
8
9
10
11
12
int main(){
int n = 100;
long long a = 1, b = 1, c = 0;
for (int i = 3; i <= n; i++) {
c = a + b;
b = a;
a = c;
cout << i << endl;
}
cout << c << endl;
return 0;
}

什么是动态规划

将原问题拆解成若干子问题,同时保存子问题的答案,使得每个子问题只求解一个,最终获得原问题的答案。【用记忆化搜索思考问题,再用动态规划实现(更简洁)】

graph TD
A(原问题问题) -->|拆解成| B(重叠子问题 - 最优子结构)
B --> C(递归问题)
C --> D(记忆化搜索--自顶向下)
C --> E(动态规划--自底向上)
D --> F((利于思考))
E --> G((实现简洁))

判断是否使用动态规划

一般询问的是最优解,并且其中含有重叠子问题。

动态规划的求解方式便是,求解重叠子问题的最优解,即最优子结构。

  • 最优解问题
题目关键字方法
#746.使用最小花费爬楼梯最小花费min(F(i - 1), F(i - 2)) + cost[i]
#120. 三角形最小路径和最小路径和min(F[i - 1][j - 1], F[i - 1][j]) + cost[i][j]
#64. 最小路径和最小路径和min(F[i][j - 1], F[i - 1][j]) + cost[j]
#343. 整数拆分最大乘积max(F[i - j] * j, (i - j) * j, F[i]) 其中j∈{1, 2…i-2, i-1}
#279. 完全平方数最少个数min(F[i - j * j]+1, F[i]) 其中j * j >= i
198. 打家劫舍最高金额max(F(i - 1), F(i - 2) + current[i])
#213. 打家劫舍 II最高金额max(不偷最后一家,不偷第一家)
#337. 打家劫舍 III最高金额max(偷父节点,不偷父节点)
#121. 买卖股票的最佳时机最大收益
#121. 买卖股票的最佳时机 II最大收益max(倒数第3天卖,倒数第3天不卖)
#309. 最佳买卖股票时机含冷冻期最大收益max(倒数第4天卖,倒数第4天不卖)
#53. 最大子序和最大和ans = max(ans+num[i], num[i])
max_ans = max(当前ans,max_ans)
  • 多少种可能性(最多的可能性)

也是最优解问题,因为每次选择都要选择最多可能性的方法。

类似于斐波拉契数列Fibonacci。

题目关键字方法
#70. 爬楼梯多少种方法F(i - 1) + F(i - 2)
#91. 解码方法多少种方法F(i - 2) + F( i - 1)
#62. 不同路径多少种路径F[i - 1][j] + F[i][j - 1]
#63. 不同路径II多少种路径F[i - 1][j] + F[i][j - 1]

#70. 爬楼梯

传送门:#70. 爬楼梯

1.记忆化搜索

n阶楼梯的可能性 = n-1阶楼梯的可能性 + n-2阶楼梯的可能性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
long long fun(int n, vector<long long> &num){    // 用数组num储存每阶台阶的可能性
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
if (num[n] == -1) {
num[n] = fun(n - 1, num) + fun(n - 2, num);
}
return num[n];
}

int main(){
int n = 10;
vector<long long> num(n+1, -1);
cout << fun(n, num) << endl;
return 0;
}

2.动态规划

1 阶楼梯的可能性 + 2 阶楼梯的可能性 = 3 阶楼梯的可能性。

从 1阶楼梯、2阶楼梯开始递推至 n阶。并用滚动数组记录需要用到的两个值,i-1阶、i-2阶。

1
2
3
4
5
6
7
8
9
10
11
int climbStairs(int n) {
int a = 2, b = 1, c = 0;
if (n == 1 ) { return b; }
if (n == 2 ) { return a; }
for (int i = 3; i <= n; i++){
c = a + b;
b = a;
a = c;
}
return c;
}

#746.使用最小花费爬楼梯

传送门:#746.使用最小花费爬楼梯

本题特殊的地方,cost = [10, 15, 20],其实一共要上 4 阶,[10, 15, 20, 0],第 4 阶为顶层,花费为 0;

因为,从 15 一次跨两阶可以到顶层。

1.记忆化搜索

第 i 阶的最小花费 = min(第 i-1 阶的最小花费,第 i-2 阶的最小花费) + 第 i 阶的费用 cost[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int DP(vector<int> &cost, int i, vector<int> &memo){
if (i == 0 || i == 1) {
memo[i] = cost[i];
}
if (memo[i] == -1) {
memo[i] = min(DP(cost, i - 1, memo), DP(cost, i - 2, memo)) + cost[i];
cout << i << " = " << memo[i] << endl;
}
return memo[i];
}

int minCostClimbingStairs(vector<int> &cost) {
cost.push_back(0);
int size = cost.size();
vector<int> memo(size, -1);
return DP(cost, size - 1, memo);
}

2.动态规划

先计算第 1 阶和第 2 阶的最小花费,由此计算 第 3 阶的最小花费;由第 2 阶和第 3 阶的最小花费计算第 4 阶的最小花费…由此递推到第 n 阶。

1
2
3
4
5
6
7
8
9
10
int minCostClimbingStairs(vector<int> &cost) {
cost.push_back(0);
int dp_1 = cost[0], dp_2 = cost[1], dp_3 = 0;
for (int i = 2; i < cost.size(); i++) {
dp_3 = min(dp_1, dp_2) + cost[i];
dp_1 = dp_2;
dp_2 = dp_3;
}
return dp_3;
}

#120. 三角形最小路径和

传送门:#120. 三角形最小路径和

1.记忆化搜索

一共有 size 层,假设从顶层到 size-2 层的每一个点的最小路径和都知道。以此为基础计算从顶层到 size-1 层的每一个点的最小路径和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
执行用时:8 ms, 在所有 C++ 提交中击败了92.89%的用户
内存消耗:9 MB, 在所有 C++ 提交中击败了
100.00%的用户
*/

int MinNum(vector<vector<int> >& triangle, int i, int j, vector<vector<int> > &memo){
/*
将到每个点最小路径和储存在二维数组 memo 中。
从底向上递归,搜索每个点的 memo[i][j]。
*/
if (i == 0) {
memo[i][0] = triangle[i][0];
} else if (memo[i][j] == 0x3f3f3f3f && j > 0 && j < i) {
memo[i][j] = min(MinNum(triangle, i - 1, j - 1, memo),
MinNum(triangle, i - 1, j, memo)) + triangle[i][j];
} else if (memo[i][j] == 0x3f3f3f3f && j == 0) {
memo[i][j] = MinNum(triangle, i - 1, j, memo) + triangle[i][j];
} else if (memo[i][j] == 0x3f3f3f3f && j == i) {
memo[i][j] = MinNum(triangle, i - 1, j - 1, memo) + triangle[i][j];
}
return memo[i][j];
}

int minimumTotal(vector<vector<int> >& triangle){
int size = triangle.size();
// 数组 memo 用来储存到每个点最小路径和。
vector<vector<int> > memo(size, vector<int>(size, 0x3f3f3f3f));
// 将最后一行的点的最小路径和储存在 min_num 中,并查找 min_num 的最小值。
vector<int> min_num;
for (int i = 0; i < size; i++) {
min_num.push_back(MinNum(triangle, triangle.size()-1, i, memo));
}
int min_ans = min_num[0];
for (int i = 1; i < min_num.size(); i++) {
if (min_num[i] < min_ans) {
min_ans = min_num[i];
}
}
return min_ans;
}

2.动态规划

从第 0 层开始,计算第 1 层的每个点的最小路径和,以第 1 层为基础,计算第 2 层的每个点的最小路径和,以此类推,并将这些最小路径和储存在数组 memo 中。

下列代码可以优化成用一维数组 memo 记录上一行的最小路径,因为计算当前行各个数的最小路径,只需要知道上一层的最小路径就可以。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
执行用时:8 ms, 在所有 C++ 提交中击败了92.89%的用户
内存消耗:8.6 MB, 在所有 C++ 提交中击败了100.00%的用户
*/
int minimumTotal(vector<vector<int> >& triangle){
int size = triangle.size();
// 将到每个点最小路径和储存在二维数组 memo 中。
vector<vector<int> > min_num(size, vector<int>(size, 0x3f3f3f3f));
for (int i = 0; i < size; i++) {
for (int j = 0; j <= i; j++) {
if (i == 0) {
min_num[i][j] = triangle[0][0];
} else if (j == 0) {
min_num[i][j] = min_num[i - 1][j] + triangle[i][j];
} else if (j == i) {
min_num[i][j] = min_num[i - 1][j - 1] + triangle[i][j];
} else {
min_num[i][j] = min(min_num[i - 1][j], min_num[i - 1][j - 1])
+ triangle[i][j];
}
}
}
int min_ans = min_num[size - 1][0];
for (int i = 1; i < min_num[size - 1].size(); i++) {
if (min_num[size - 1][i] < min_ans) {
min_ans = min_num[size - 1][i];
}
}
return min_ans;
}

其实我们发现,将计算第 i 层各点的最小路径和时,只需要知道第 i-1 层各点的最小路径和。所以我们只需要用一个 size 大小的数组,储存第 i-1 层的各层的最小路径和,并不需要用 size * size 大小的二维数组,储存所有点的最小路径和。

虽然以上的方法节省了空间,但是相对应的时间也会更长。用空间换时间还算划算。

#64. 最小路径和

传送门:#64. 最小路径和

1.动态规划

这道题和 #120. 三角形最小路径和 思路十分相似,直接自顶向下用动态规划写了。

下列代码可以优化成用一维数组 memo 记录上一行的最小路径,因为计算当前行各个数的最小路径,只需要知道上一层的最小路径就可以。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int size = grid.size();
if (size == 0) {
return 0;
}
int row = grid[0].size();
// 用数组 memo 储存到每个点的最小路径和。
vector<vector<int> > memo(size, vector<int>(row, 0x3f3f3f3f));
for (int i = 0; i < size; i++) {
for (int j = 0; j < row; j++) {
if (i == 0 && j == 0) {
memo[i][j] = grid[0][0];
} else if (j == 0) {
memo[i][j] = memo[i - 1][j] + grid[i][j];
} else if (i == 0) {
memo[i][j] = memo[i][j - 1] + grid[i][j];
} else {
memo[i][j] = min(memo[i][j - 1], memo[i - 1][j]) + grid[i][j];
}
}
}
return memo[size - 1][row - 1];
}
};

#343. 整数拆分

传送门:#343. 整数拆分

1.记忆化搜索

n的最大拆分 = max( 1*[n-1]的最大拆分,1*[n-1],2*[n-2]的最大拆分,2*[n-2]…[n-1]*1的最大拆分,[n-1]*1)。

其中,我将 max(i*[n-i]的最大拆分,i*[n-i]) 存入 memo[n] 中,并下一个循环中,比较出 max(i*[n-i]的最大拆分,i*[n-i],memo[n])。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> memo;

int Max3(int a, int b, int c){
return max(a, max(b, c));
}

int MaxBreak(int n){
if (n == 1) {
return 1;
}
if (memo[n] != -1) {
return memo[n];
}
for (int i = 1; i <= n; i++) {
memo[n] = Max3(i * MaxBreak(n - i), i * (n - i), memo[n]);
}
return memo[n];
}

int integerBreak(int n) {
memo = vector<int>(n + 1, -1);
return MaxBreak(n);
}

2.动态规划

n的最大拆分 = max( 1*[n-1]的最大拆分,1*[n-1],2*[n-2]的最大拆分,2*[n-2]…[n-1]*1的最大拆分,[n-1]*1)。

我们自底向上,从 1 计算到 n的最大拆分。

1的最大拆分 = 1;

2的最大拆分 = max(1*[2-1]的最大拆分,1*[2-1]);

3的最大拆分 = max(1*[3-1]的最大拆分,1*[3-1],2*[3-2]的最大拆分,2*[3-2])

其中,我将 max(1*[3-1]的最大拆分,1*[3-1]) 存入 memo[3] 中,并下一个循环中,比较出 max(2*[3-2]的最大拆分,2*[3-2],memo[3])。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Max3(int a, int b, int c){
return max(a, max(b, c));
}

int integerBreak(int n) {
// 用数组 memo 储存从 1 到 n 的最大拆分乘积。
vector<int> memo(n + 1, -1);
memo[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
// 关键的递推公式
memo[i] = Max3(j * memo[i - j], j * (i - j), memo[i]);
}
}
return memo[n];
}

#279. 完全平方数

传送门:#279. 完全平方数

1.动态规划

自底向上分析,(为方便表述,拆分成完全平方数,最少个数表示为 F),

F1 = 1;(1 为完全平方数)

F2 = 2;(F2 = F1 + F1)

F3 = 3;(F3 = F2 + F1)

F4 = 1;(4 本身是完全平方数,故 F4 = 1)

F5 = 2;(F5 = (F4 + F1)

F6 = 3;(F6 = min((F5 + F1),(F4 + F2))

每次拆解,n - 一个完全平方数A = 另外一个数B;另外一个数B - 一个完全平方数C = 另外一个数D…

via:leetcode题解中的一个图,和我想法一致。(其中 F1、F4、F9…等完全平方数的最少个数等于 1,图中用 +1表示)numSquares

1
2
3
4
5
6
7
8
9
10
11
int numSquares(int n) {
vector<int> min_num(n + 1, 0x7fffffff);
min_num[0] = 0;
min_num[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; i - j * j >= 0; j++) {
min_num[i] = min(min_num[i - j * j] + 1, min_num[i]);
}
}
return min_num[n];
}

#91. 解码方法

传送门:#91. 解码方法

**PS:**此题有些特殊的数据需要注意,“0”、“00”、“100”、“01”,应处理好边界判断的问题。

1.深度优先搜索

以 1234 为例,如下图,

先深入左子树, 1、2、3、4 递归到底,成功;

再返回 2,进入 34,非法;

再返回 1,继续递归至 23、4,成功;

再返回开始,递归右子树,12、3、4,成功;

再返回 12,进入 34,非法。

深搜完成。

graph TD
A(开始) --> B(1)
B --> C(2)
C --> D(3)
D --> E(4)
E --> P((成功))
A --> F(12)
B --> G(23)
G --> O(4)
O --> Q((成功))
C --> K(34)
K --> S((非法))
F --> L(3)
F --> M(34)
M --> T((非法))
L --> N(4)
N --> R((成功))

虽然思路极其简单清晰,在本地IDE也可以AC,但是递归压栈过多,数据规模稍大就会超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int num = 0;
void dfs(string s, int index, int n){
if (index == n) { // 递归退出条件
num++;
return;
}
if (s[index + 1] != '0') {
dfs(s, index + 1, n); // 1个数字单独解码,也就是遍历index节点的左子树
if (index + 2 <= n && (s[index + 1] - '0') < 3
&& (s[index + 1] - '0') * 10 + (s[index + 2] - '0') <= 26) {
dfs(s, index + 2, n); // 2个数字合并解码,也就是遍历index节点的右子树
}
}
return;
}

int numDecodings(string s) {
int n = s.length() - 1;
dfs(s, -1, n);
return num;
}

2.动态规划

以1224为例,字符串的解码方式数量用 F 表示,

F(“1”) = 1

F(“12”) = F(“1”) + F(“”)

F(“122”) = F(“12”) + F(“1”)

F(“1221”) = F(“122”) + F(“12”)

以 F(“1221”) 为例,让尾数1单独解码的方式数量为 F(“122”),让 1 和前面的 2 合并解码方式数量为 F(“12”)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int numDecodings(string s) {
if (s[0] == '0') {
return 0;
}
s = '0' + s; // 此处为了解决 F("") = 1 的问题
int n = s.length();
vector<int> memo(n, 0);
memo[0] = 1; // 此处为了解决 F("") = 1 的问题
memo[1] = 1;
for (int i = 2; i < n; i++) {
if (s[i] != '0') {
memo[i] += memo[i - 1];
}
if (s[i - 1] != '0' && s[i - 1] - '0' < 3) {
if (s[i - 1] - '0' < 2 || s[i] - '0' < 7) {
memo[i] += memo[i - 2];
}
}
}
return memo[n - 1];
}

#62. 不同路径

传送门:#62. 不同路径

PS:对于m*n矩形,用二维数组表示为 memo[n][m],n 表示行。

1.动态规划

从左上角开始,从左到右、从上至下的遍历,记录到达每一个点的不同路径的数量,并放在 memo 二维数组中记录,以此计算出 右下角的点的值。

以下视频引用于leetcode题解,简单易通。

1
2
3
4
5
6
7
8
9
10
11
12
13
int uniquePaths(int m, int n) {
vector<vector<int> > memo(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == 0 || j == 0) {
memo[i][j] = 1;
} else {
memo[i][j] = memo[i - 1][j] + memo[i][j - 1];
}
}
}
return memo[n - 1][m - 1];
}

2.优化

优化前:

执行用时:4 ms, 在所有 C++ 提交中击败了30.17%的用户

内存消耗:6.4 MB, 在所有 C++ 提交中击败了100.00%的用户

优化后:

执行用时:0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗:6.1 MB, 在所有 C++ 提交中击败了100.00%的用户

当计算第3行第4个点(3, 4)时,只需要知道 (3, 3)和 (2, 4)。

所以,当计算第3行时,只需要知道第2行的所有值就行。

故我们使用一维数组 memo 来记录 i-1 行的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
int uniquePaths(int m, int n) {
vector<int> memo(m, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == 0 || j == 0) {
memo[j] = 1;
} else {
memo[j] = memo[j] + memo[j - 1];
}
}
}
return memo[m - 1];
}

#63. 不同路径II

传送门:#63. 不同路径II

PS:这题需要判断条件过多,使用一维数组可能会超时;建议空间换时间,使用二维数组。

1.动态规划

#62. 不同路径 的基础上,增加判断 if (obstacleGrid[0][i] == 0)

需要注意的是,当第1行或者第1列出现 1的时候,1之后的点 ,memo 值 = 0;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if (obstacleGrid[0][0] == 1) {
return 0;
}
int n = obstacleGrid.size();
int m = obstacleGrid[0].size();
vector<vector<int> > memo(n, vector<int>(m, 0));
for (int i = 0; i < m; i++) { // 先处理第一行的值
if (obstacleGrid[0][i] == 0) {
memo[0][i] = 1;
} else {
break; // 出现 1,其后的点的 memo = 0
}
}
for (int i = 1; i < n; i++) { // 再处理第一列的值
if (obstacleGrid[i][0] == 0) {
memo[i][0] = 1;
} else {
break; // 出现 1,其后的点的 memo = 0
}
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (obstacleGrid[i][j] == 0) {
memo[i][j] = memo[i - 1][j] + memo[i][j - 1];
}
}
}
return memo[n - 1][m - 1];
}

#198. 打家劫舍

传送门:#198. 打家劫舍

1.动态规划

先求出只有1栋房子的最大金额memo[0],再求出只有2栋房子的最大金额memo[1],有3栋房子的最大金额为 max(memo[0] + nums[2], memo[1])。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int rob(vector<int>& nums) {
int size = nums.size();
if (size == 0) {
return 0;
}
if (size == 1) {
return nums[0];
}
if (size == 2) {
return max(nums[0], nums[1]);
}
vector<int> memo(size, -1); // memo[i] 表示前i-1栋房子,能偷到的最大金额
memo[0] = nums[0];
memo[1] = max(nums[0], nums[1]);
for (int i =2; i < size; i++) {
memo[i] = max((memo[i - 2] + nums[i]), memo[i - 1]);
}
return memo[size - 1];
}

#213. 打家劫舍 II

传送门:#213. 打家劫舍 II

1.动态规划

环形问题,第一个和最后一个不能同时偷窃。所以我们有两种选择:

  • 不偷最后一个房子,偷第 1 个房子到第 n-1 个房子,记为 [1, n - 1] 。
  • 不偷第一个房子,偷第 2 个房子到第 n 个房子,记为 [2, n]。

所以在 #198. 打家劫舍 的基础上,我只需计算 [1, n - 1] 的最大金额、[2, n] 的最大金额,二者中的最大的值便是所求。

在细节上,我们用数组 memo_1 储存 [1, n - 1] 中的最优子结构;用 memo_2 储存 [2, n] 中的最优子结构。在求 [2, n] 的最大金额过程中,我们只需设 memo[1] = 0 即可,也就代表只有一个房子的时候,最大金额等于0,也就是不偷第一个房子的意思。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
if (n == 1) {
return nums[0];
}
vector<int> memo_1(n+1, 0);
vector<int> memo_2(n+1, 0);
// 求解memo_1[n - 1]
memo_1[0] = 0;
memo_1[1] = nums[0];
memo_1[2] = max(nums[0], nums[1]);
for (int i = 3; i <= n - 1; i++) {
memo_1[i] = max(memo_1[i - 1], memo_1[i - 2] + nums[i - 1]);
}
// 求解memo_2[n]
memo_2[0] = 0;
memo_2[1] = 0;
memo_2[2] = nums[1];
for (int i = 3; i <= n; i++) {
memo_2[i] = max(memo_2[i - 1], memo_2[i - 2] + nums[i - 1]);
}

return max(memo_2[n], memo_1[n - 1]);
}

#337. 打家劫舍 III

传送门:#337. 打家劫舍 III

1.暴力递归

  • 方案一(偷父节点):父节点的值 + 左儿子的左儿子最大金额 + 左儿子的右儿子最大金额 + 右儿子的左儿子的最大金额 + 右儿子的右儿子的最大金额
  • 方案二(不偷父节点):左儿子的最大金额 + 右儿子的最大金额

取方案一和方案二的最大值,为父节点的最大金额。

一图胜千言:

1
2
3
4
5
6
7
8
9
10
11
12
13
int rob(TreeNode* root) {
if(root == NULL) {
return 0;
}
int sum = root->val;
if (root->left != NULL) {
sum += rob(root->left->left) + rob(root->left->right);
}
if (root->right != NULL) {
sum += rob(root->right->left) + rob(root->right->right);
}
return max(sum, rob(root->right) + rob(root->left));
}

2.记忆化搜索

减少递归次数,将每一个节点的最大金额,保存在哈希表(字典)中。(线性结构使用数组做备忘录,树状结构使用哈希表做备忘录)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
unordered_map<TreeNode*,int> hash;     // 注意:键是指针,不是节点。
int rob(TreeNode* root) {
if(root == NULL) {
return 0;
}
if (hash.count(root) == 1) {
return hash[root];
}
int sum = root->val;
if (root->left != NULL) {
sum += rob(root->left->left) + rob(root->left->right);
}
if (root->right != NULL) {
sum += rob(root->right->left) + rob(root->right->right);
}
hash[root] = max(sum, rob(root->right) + rob(root->left));
return hash[root];
}

#121. 买卖股票的最佳时机

传送门:#121. 买卖股票的最佳时机

1.动态规划

这题比较简单,为后面做铺垫。

max_rofit[i] = max(max_rofit[i - 1], prices[i] - min_prices)

min_prices = min(min, prices[i])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int maxProfit(vector<int>& prices) {
const int n = prices.size();
if (n == 0) {
return 0;
}
int min = prices[0];
int res = 0;
for (int i = 1; i < n; i++) {
if (prices[i] < min) {
min = prices[i];
} else {
res = max(prices[i] - min, res);
}
}
return res;
}

#122. 买卖股票的最佳时机 II

传送门:#121. 买卖股票的最佳时机 II

先总结一下,递推:max(倒数第二天买的情况,倒数第二天不买的情况)。

再具体来看,我们先想象一个普通的场景:[1, 2, 3, 4],股票一直涨。

前 i 个元素的最大利润 = 前 i - 1 个元素的最大利润 + 当前元素的价格 prices[i - 1] - 前一个元素的价格 prices[i - 2] (倒数第二天买的情况)。

当然了股票跌的可能性:[1, 4, 3, 2]。

如果 当前元素的价格 prices[i - 1] < 前一个元素的价格 prices[i - 2]。前 i 个元素的最大利润 = 前 i - 1 个元素的最大利润(倒数第二天不买的情况)。

1
2
3
4
5
6
7
8
9
10
11
12
13
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (n < 2) {
return 0;
}
vector<int> memo(n + 1, 0);
memo[0] = 0;
memo[1] = 0;
for (int i = 2; i <= n; i++) {
memo[i] = prices[i - 1] > prices[i -2] ? memo[i - 1] + prices[i - 1] - prices[i - 2] : memo[i - 1];
}
return memo[n];
}

#309. 最佳买卖股票时机含冷冻期

传送门:#309. 最佳买卖股票时机含冷冻期

记录前 i-1 天的最大值为 key。

graph TD
A(第 i 天的最大利润) --> B(第 i 天价格 是否 大于 key)
B -->|是| C(比较两种情况)
B -->|否| D(第 i 天最大利润 = 第 i-1 天最大利润)
C --> E(第 i-1 天最大利润 + 第 i 天价格 - key)
C --> F(第 i-3 天最大利润 + 第 i 天价格 - 第 i - 1天价格)
E --> G(二者取最大值)
F --> G
  • **第 i-1 天最大利润 + 第 i 天价格 - key:**这种情况是股票一直涨的情况,所以只需要一直加差价就可以了。比如:[1, 2, 3, 4, 5, 6]。

  • **第 i-3 天最大利润 + 第 i 天价格 - 第 i - 1天价格:**这种情况是中间有几天暴跌,适合先卖出股票,再低价买回来,赚取差价。比如:[2, 7, 1, 1, 7]。

    为什么要取第 i-3 天最大利润呢?因为有冷冻期,卖出股票不可以第二天立马买股票,要隔一天。

  • **第 i 天最大利润 = 第 i-1 天最大利润:**比如:[1, 9, 1, 1],第 3 天的收入 = 第 2 天的收入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (n < 2) {
return 0;
}
if (n == 2) {
return prices[1] > prices[0] ? prices[1] - prices[0] : 0;
}
int key = 0;
vector<int> memo(n + 1, 0); // memo[i] 表示第 i 天的最大收益
memo[0] = 0;
memo[1] = 0;
if (prices[1] > prices[0]) {
memo[2] = prices[1] - prices[0];
key = prices[1];
} else {
memo[2] = 0;
key = prices[0];
}
for (int i = 3; i <= n; i++) {
if (prices[i - 1] > key) {
// 第 i-1 天最大利润 + 第 i 天价格 - 前 i-1 天的最大值
memo[i] = memo[i - 1] + prices[i - 1] - key;
key = prices[i - 1];
} else {
memo[i] = memo[i - 1];
}
// 第 i-3 天最大利润 + 第 i 天价格 - 前 i-1 天的价格
int tmp = memo[i - 3] + prices[i - 1] - prices[i - 2];
if (tmp > memo[i]) {
key = prices[i - 1];
memo[i] = tmp;
}
}
return memo[n];
}

#53. 最大子序和

传送门:#53. 最大子序和

用 ans 表示以 nums[i] 为结尾的最大序列和。

以 nums[i] 为结尾的最大序列和,要么是 nums[i],要么是 num[i - 1] 的 ans + num[i]。

最后返回的答案也是在 n 个 ans 中选出最大值。

1
2
3
4
5
6
7
8
int maxSubArray(vector<int>& nums) {
int n = nums.size(), ans = 0, max_ans = nums[0];
for (int i = 0; i < n; i++) {
ans = max(ans + nums[i], nums[i]);
max_ans = max(max_ans, ans);
}
return max_ans;
}

#LCP 19. 秋叶收藏集

传送门:LCP 19.秋叶收藏集

这道题非常特别!

使用三个数组,dp[i][0]、dp[i][1]、dp[i][2] 。

  • dp[i][0]:前 i + 1 个元素,全是红,比如 rrrrr,最少需要多少次调整。

  • dp[i][1]:前 i + 1 个元素,满足前面是红,后面是黄,比如 rrrryyyy,最少需要多少次调整。

  • dp[i][2]:前 i + 1 个元素,满足前面后面是红,中间是黄,比如 rrryyyrrr,最少需要多少次调整。

状态转移关系:

  • dp[i][0] 等于 dp[i - 1][0] + 最后一个元素是不是红色。

    dp[i][0] = dp[i - 1][0] + (leaves[i] == 'r' ? 0 : 1)

  • dp[i][1] 等于 min( dp[i - 1][0] + 最后一个元素是不是黄色,dp[i - 1][1] + 最后一个元素是不是黄色 )。

    dp[i][1] = min(dp[i - 1][1] + (leaves[i] == 'y' ? 0 : 1), dp[i - 1][0] + (leaves[i] == 'y' ? 0 : 1));

  • dp[i][2] 等于 min( dp[i - 1][1] + 最后一个元素是不是红色,dp[i - 1][2] + 最后一个元素是不是红色 )。

    dp[i][2] = min(dp[i - 1][1] + (leaves[i] == 'r' ? 0 : 1), dp[i - 1][2] + (leaves[i] == 'r' ? 0 : 1));

PS:注意 pd 初始状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
int minimumOperations(string leaves) {
int leaves_size = leaves.size();
vector< vector<int> > dp(leaves_size, vector<int>(3, 0));
for (int i = 0; i < leaves_size; i++) {
// 红
if (i < 1) {
dp[i][0] = (leaves[i] == 'r' ? 0 : 1);
} else {
dp[i][0] = dp[i - 1][0] + (leaves[i] == 'r' ? 0 : 1);
}

// 红黄
if (i < 1) {
dp[i][1] = dp[i][0];
} else {
dp[i][1] = min(dp[i - 1][1] + (leaves[i] == 'y' ? 0 : 1), dp[i - 1][0] + (leaves[i] == 'y' ? 0 : 1));
}

// 红黄红
if (i < 2) {
dp[i][2] = dp[i][1];
} else {
dp[i][2] = min(dp[i - 1][1] + (leaves[i] == 'r' ? 0 : 1), dp[i - 1][2] + (leaves[i] == 'r' ? 0 : 1));
}
}
return dp[leaves_size - 1][2];
}
};

leetcode|动态规划
https://www.aimtao.net/dynamic-programming/
Posted on
2020-07-11
Licensed under