# 动态规划的解题步骤
- 设计状态
- 写出状态转移方程
- 设定初始状态
- 执行状态转移
- 返回最终的解
# 动态规划和贪心的区别
- 贪心：每一步都做出当时看起来最佳的选择，也就是说，它总是做出局部最优的选择。
- 动态规划：每一个状态一定是由上一个状态推导出来的。
# 01背包问题详解
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
状态转移方程
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
# 二维数组方法
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagWeight = 4;
vector<vector<int>> dp(weight.size(), vector<int>(bagWeight + 1, 0));
for (int j = weight[0]; j <= bagWeight; j++) {
dp[0][j] = value[0];
}
for (int i = 1; i < weight.size(); i++) {
for (int j = 0; j <= bagWeight; j++) {
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 一维数组方法
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagWeight = 4;
vector<int> dp(bagWeight + 1, 0);
for (int i = 0; i < weight.size(); i++) {
for (int j = bagWeight; j >= weight[i]; j--) {
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 为什么一维数组需要倒序，而二维数组不需要倒序？
- 对于二维数组来说，上一次的状态是由dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖！
- 而对于一维数组来说，如果正序遍历，会导致复用上一状态的结果，也就是状态会被累加
# 一维dp可不可以调换遍历顺序？
答案必须是不可以！如果调换顺序，会导致dp[j]只会被更新一次，因为dp[j]依赖的上一级状态并没有更新，这就导致了该背包只会被放入一个或者0个物品。
# 完全背包问题详解
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
状态转移方程
dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
# 二维数组方法
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagWeight = 4;
vector<vector<int>> dp(weight.size(), vector<int>(5, 0));
for (int j = weight[0]; j <= bagWeight; j++) {
dp[0][j] = max(value[0], value[0] + dp[0][j - weight[0]]);
}
for (int i = 1; i < weight.size(); i++) {
for (int j = 0; j <= bagWeight; j++) {
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 一维数组方法
- 先物品，后容量
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagWeight = 4;
vector<int> dp(bagWeight + 1, 0);
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
- 先容量，后物品
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagWeight = 4;
vector<int> dp(bagWeight + 1, 0);
for (int j = 0; j <= bagWeight; j++) { // 遍历背包容量
for (int i = 0; i < weight.size(); i++) { // 遍历物品
if ((j - weight[i]) >= 0) {
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
二者区别
- 如果是普通的纯完全背包，那么这两个for循环顺序没有影响
- 如果需要计算组合或者排序数量那么就有影响
- 如果求组合数就是外层for循环遍历物品，内层for遍历背包
- 如果求排列数就是外层for遍历背包，内层for循环遍历物品
