前言
动态规划（Dynamic Programming）（dp）描述。
一、核心概念
二、典型问题
类型1：
类型2：依据力扣分类
- 基础问题
- 背包问题
- 打家劫舍问题
- 股票问题
- 子序列问题
类型3：
非线性树型如：337.打家劫舍 III - 力扣（LeetCode）——中等
三、算法步骤
- 确定dp数组中下标和值的含义 -> 确定dp数组的维度、规模和所求结果/返回值
- 确定dp数组的状态转移方程/递推公式
- 确定dp数组的初始化值
- 确定dp数组的遍历顺序和临界条件
- 模拟/举例推导dp数组以验证
算法往往为多重循环而不容易模拟/举例推导dp数组以验证。可在调试时再验证。
四、模板示例
509.斐波那契数 - 力扣（LeetCode）——简单的题解：
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
| class Solution
{
public:
int fib(int n)
{
if (n == 0 || n == 1)
{
return n;
}
vector<int> dp(n + 1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; ++i)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};
|
五、调试方法
- 输出dp数组
- 判断是否和模拟/举例推导的dp数组一致
- 若不一致，则可能是算法步骤问题
- 若一致，则可能是细节问题
六、性能分析
- 时间复杂度：一般为多重循环的性能
- 空间复杂度：一般为dp数组的规模
七、优化方法
1. 记忆化搜索
作用：降低时间复杂度，增加空间复杂度
描述：
- 使用数据结构存储已计算的状态
- 不再重复计算状态
- 从数据结构获取已计算的状态
可能的优化：O(n²) -> O(n)。n为数据规模
2. 滚动数组
作用：优化空间复杂度
描述：
- 状态推导时
- 若后一个状态只依赖固定的前一个或多个状态
- 则无需定义相应数据规模的dp数组
- 只需定义状态依赖规模的dp数组或变量
- 在递推中不断更新该dp数组或变量为前一个或多个所求解的状态，再用于求解后一个状态
可能的优化：O(n) -> O(1)；O(m × n) -> O(n)
八、背包问题
1. 类型
混合背包：
- 0-1背包 （基础）：各物品数量为一
- 完全背包：各物品数量不限
- 多重背包：各物品数量不同
分组背包：依组装包，每组数量为一
2. 算法步骤
- 分析应用问题转换为背包问题 -> 确定背包问题的参数
背包：容量
物品：体积，价值，数量
- 确定dp数组中下标和值的含义 -> 确定dp数组的维度、规模和所求结果/返回值
- 确定dp数组的状态转移方程/递推公式
- 确定dp数组的初始化值
- 确定dp数组的遍历顺序和临界条件
- 确定dp数组的返回值
- 模拟/举例推导dp数组以验证
3. 模板示例：0-1背包问题
详细解释参见：代码随想录 (programmercarl.com)
二维dp数组：
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include <vector>
#include <iostream>
using std::vector;
using std::cout;
using std::endl;
void func()
{
int capacity = 4;
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int quantity = 3;
vector<vector<int>> dp(quantity, vector<int>(capacity + 1));
for (int j = 0; j < weight[0]; ++j)
{
dp[0][j] = 0;
}
for (int j = weight[0]; j <= capacity; ++j)
{
dp[0][j] = value[0];
}
for (int i = 1; i < quantity; ++i)
{
for (int j = 0; j <= capacity; ++j)
{
if (j < weight[i])
{
dp[i][j] = dp[i - 1][j];
}
else
{
dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
}
cout << dp[quantity - 1][capacity] << endl;
}
int main()
{
func();
}
|
二维dp数组可先遍历物品，后正序遍历背包：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
for (int i = 1; i < quantity; ++i)
{
for (int j = 0; j <= capacity; ++j)
{
if (j < weight[i])
{
dp[i][j] = dp[i - 1][j];
}
else
{
dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
}
|
二维dp数组可先遍历背包，后正序遍历物品：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
for (int j = 0; j <= capacity; ++j)
{
for (int i = q; i <= quantity; ++i)
{
if (j < weight[i])
{
dp[i][j] = dp[i - 1][j];
}
else
{
dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
}
|
一维dp数组只能先遍历物品，后倒序遍历背包：
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
| #include <vector>
#include <iostream>
using std::cout;
using std::endl;
using std::vector;
void func()
{
int capacity = 4;
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int quantity = 3;
vector<int> dp(capacity + 1, 0);
for (int i = 0; i < quantity; ++i)
{
for (int j = capacity; j >= weight[i]; --j)
{
dp[j] = std::max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << dp[capacity] << endl;
}
int main()
{
func();
}
|
注意：还存在三维或更高维dp数组。如：474.一和零 - 力扣（LeetCode）——中等
4. 模板示例：完全背包问题
详细解释参见：代码随想录 (programmercarl.com)
一维dp数组：
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
| #include <vector>
#include <iostream>
using std::cout;
using std::endl;
using std::vector;
void func()
{
int capacity = 4;
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int quantity = 3;
vector<int> dp(capacity + 1, 0);
for (int i = 0; i < quantity; ++i)
{
for (int j = weight[i]; j <= capacity; ++j)
{
dp[j] = std::max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << dp[capacity] << endl;
}
int main()
{
func();
}
|
一维dp数组可先遍历物品，后正序遍历背包：
1
2
3
4
5
6
7
8
9
10
11
|
for (int i = 0; i < quantity; ++i)
{
for (int j = weight[i]; j <= capacity; ++j)
{
dp[j] = std::max(dp[j], dp[j - weight[i]] + value[i]);
}
}
|
一维dp数组可先遍历背包，后正序遍历物品：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
for (int j = 0; j <= capacity; ++j)
{
for (int i = 0; i < quantity; ++i)
{
if (j - weight[i] >= 0)
{
dp[j] = std::max(dp[j], dp[j - weight[i]] + value[i]);
}
}
}
|
若求排列数，则先遍历背包，后遍历物品
若求组合数，则先遍历物品，后遍历背包
5. 模板示例：多重背包
详细解释参见：代码随想录 (programmercarl.com
九、力扣例题
题目组织依据：代码随想录 (programmercarl.com)
基础问题：
- 509.斐波那契数——简单
- 70.爬楼梯——简单
- 746.使用最小花费爬楼梯——简单
- 62.不同路径——中等
- 63.不同路径 II——中等
- 343.整数拆分——中等
- 96.不同的二叉搜索树——中等
背包问题：0-1背包问题
- 416.分割等和子集——中等
- 1049.最后一块石头的重量 II——中等
- 494.目标和——中等
- 474.一和零——中等
背包问题：完全背包问题
- 518.零钱兑换 II——中等
- 377.组合总和 Ⅳ——中等
- 70.爬楼梯——简单
- 322.零钱兑换——中等
- 279.完全平方数——中等
- 139.单词拆分——中等
打家劫舍问题：
- 198.打家劫舍——中等
- 213.打家劫舍 II——中等
- 337.打家劫舍 III——中等
股票问题：
- 121.买卖股票的最佳时机——简单
- 122.买卖股票的最佳时机 II——中等
- 123.买卖股票的最佳时机 III——困难
- 188.买卖股票的最佳时机 IV——困难
- 309.最佳买卖股票时机含冷冻期——中等
- 714.买卖股票的最佳时机含手续费——中等
子序列问题：非连续和连续子序列问题
- 300.最长递增子序列——中等
- 674.最长连续递增序列——简单
- 718.最长重复子数组——中等
- 1143.最长公共子序列——中等
- 1035.不相交的线——中等
- 53.最大子数组和——中等
子序列问题：编辑距离问题
- 392.判断子序列——简单
- 115.不同的子序列——困难
- 583.两个字符串的删除操作——中等
- 72.编辑距离——困难
子序列问题：回文问题
- 647.回文子串——中等
- 516.最长回文子序列——中等
总结
动态规划（Dynamic Programming）（dp）描述。
参考资料
