理解动态规划 ~ 知乎好文
LeetCode简单的动态规划题：
LeetCode较难的动态规划题：
总结：
动态规划与其说是一个算法，不如说是一种方法论。
该方法论主要致力于将“合适”的问题拆分成三个子目标一一击破：
- 1.建立状态转移方程
- 2.缓存并复用以往结果
- 3.按顺序从小往大算
概念：有N件物品和一个最多能装重量为W 的背包。第i件物品的重量是weight[i]，价值是value[i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
本案例视频链接 ~ 尚硅谷
分析：
图解分析：
案例分析：
1. 假如现在只有 吉他(G) ， 这时不管背包容量多大，只能放一个吉他1500(G)
2. 假如有吉他和音响, 验证公式:v[1][1] =1500
(1). i = 1, j = 1
(2). w[i] = w[1] = 1 j = 1
v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]} :
v[1][1] = max {v[0][1], v[1] + v[0][1-1]} = max{0, 1500 + 0} = 1500
3. 假如有吉他/音响/电脑, 验证公式:v[3][4]
(1). i = 3；j = 4
(2). w[i] = w[3] =3 j = 4
j = 4 >= w[i] = 3 => 4 >= 3
v[3][4] = max {v[2][4], v[3] + v[2][1]} = max{3000, 2000+1500} = 2000+1500
归纳：
从表格的右下角开始回溯，如果发现前n个物品的最佳组合的价值和前n-1个物品最佳组合的价值一样，说明第n个物品没有被装入；否则，第n个物品被装入。
问题：背包容量为4时，能装入物品的最大价值是多少？
代码：第一种写法
const w = [1, 4, 3]; //物品重量
const value = [1500, 3000, 2000]; //物品的价值
const m = 4; //背包容量
const n = 3; //物品的个数
// 二维数组：v[i][j] 表示在前i个物品中能够装入容量为j的背包中的最大价值
let v = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));
// i控制行，j控制列
for (let i = 1; i <= n; i++) { // 先遍历物品
for (let j = 1; j <= m; j++) { // 后遍历背包容量
// 这里使用w[i - 1]是避免跳过第一个物品，同理else中的语句也是一样的
if (w[i - 1] > j) {
v[i][j] = v[i - 1][j];
} else {
v[i][j] = Math.max(v[i - 1][j], value[i - 1] + v[i - 1][j - w[i - 1]]);
}
}
}
// for (let j = 1; j <= m; j++) { //先遍历背包容量
// for (let i = 1; i <= n; i++) { //后遍历物品
// if (w[i - 1] > j) {
// v[i][j] = v[i - 1][j];
// } else {
// v[i][j] = Math.max(v[i - 1][j], value[i - 1] + v[i - 1][j - w[i - 1]]);
// }
// }
// }
console.log(v[n][m]); //3500
// 二维数组v的结果如下：
// [
// [0, 0, 0, 0, 0],
// [0, 1500, 1500, 1500, 1500],
// [0, 1500, 1500, 1500, 3000],
// [0, 1500, 1500, 2000, 3500]
// ]
// 复杂度分析
// 时间复杂度：O(m*n)
// 空间复杂度：O(m*n)
问题：为何既可以先遍历物品，也可以先遍历背包的容量呢？（为何for循环遍历次序可以不同？）
答：由递推公式可以看出，v[i][j] 是靠 v[i-1][j] 和 v[i - 1][j - w[i-1]] 推导出来的，v[i-1][j] 和 v[i - 1][j - w[i-1]] 都位于 v[i][j] 的左上角方向（包括正上方向），即先打印行或者列，都不影响 v[i][j] 公式的推导。
代码：第二种写法【原理与第一种一样，只不过初始化的过程略有调整】
const w = [1, 4, 3]; //物品重量
const value = [1500, 3000, 2000]; //物品的价值
const m = 4; //背包容量
const n = 3; //物品的个数
let v = new Array(n).fill(0).map(() => new Array(m + 1).fill(0));
// 初始化
for (let j = w[0]; j <= m; j++) {
v[0][j] = value[0];
}
for (let i = 1; i < n; i++) { //先遍历物品
for (let j = 0; j <= m; j++) { //后遍历背包容量
// 初始化时，第一个物品已经安排上了(第一行打印完成)，故不需要w[i-1]了
if (w[i] > j) {
v[i][j] = v[i - 1][j];
} else {
v[i][j] = Math.max(v[i - 1][j], value[i] + v[i - 1][j - w[i]]);
}
}
}
// for (let j = 0; j <= m; j++) { //先遍历背包容量
// for (let i = 1; i < n; i++) { //后遍历物品
// if (w[i] > j) {
// v[i][j] = v[i - 1][j];
// } else {
// v[i][j] = Math.max(v[i - 1][j], value[i] + v[i - 1][j - w[i]]);
// }
// }
// }
console.log(v);
// 二维数组v的结果如下：
// [
// [0, 1500, 1500, 1500, 1500],
// [0, 1500, 1500, 1500, 3000],
// [0, 1500, 1500, 2000, 3500]
// ]
优化代码：将空间复杂度降为O(n)。
二维数组变一维数组： 在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
const w = [1, 3, 4];
const value = [15, 20, 30];
const n = 4; //背包最大容量
const m = w.length; //物品的个数
let dp = new Array(n + 1).fill(0);
for (var i = 1; i <= m; i++) {
for (var j = n; j >= w[i - 1]; j--) {
dp[j] = Math.max(dp[j], dp[j - w[i - 1]] + value[i - 1]);
// dp[j]: 未放当前物品---> 因为是倒序的，初始化的时候空
// dp[j - w[i - 1]：剩余背包容量所能装入物品的最大价值
// value[i - 1]当前物品的价值
}
}
console.log(dp);//[ 0, 15, 15, 20, 35 ]
注意要点：
原因：倒叙遍历是为了保证物品 i 只被放入一次！一旦正序遍历了，那么物品就会被重复加入多次！
原因：实际上是把dp[i - 1]那一层拷贝到dp[i]上。
LeetCode中 “01背包” 题型汇总：
- 分割等和子集：转化后为0-1背包可行性问题。
- 目标和：转化问题以后为0-1背包方案数问题。
- 最后一块石头的重量 II：转化后为0-1背包最小值问题。
- 474. 一和零：两个维度的01背包
概念：有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，价值是value[i]。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
代码：
const w = [1, 3, 4];
const value = [15, 20, 30];
const n = 4; //背包最大容量
const m = w.length; //物品的个数
let dp = new Array(m + 1).fill(0).map(v => new Array(n + 1).fill(0));
for (var i = 1; i <= m; i++) {
for (var j = 1; j <= n; j++) {
for (var k = 0; k <= j / w[i - 1]; k++) {
if (w[i - 1] > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], k * value[i - 1] + dp[i][j - k * w[i - 1]]);
}
}
}
}
console.log(dp);
// [
// [0, 0, 0, 0, 0],
// [0, 15, 30, 45, 60],
// [0, 15, 30, 45, 60],
// [0, 15, 30, 45, 60]
// ]
优化代码：将空间复杂度降为O(n)。二维数组变一维数组
视频链接：完全背包问题
const w = [1, 3, 4];
const value = [15, 20, 30];
const n = 4; //背包最大容量
const m = w.length; //物品的个数
let dp = new Array(n + 1).fill(0);
for (var i = 1; i <= m; i++) {
for (var j = n; j >= w[i - 1]; j--) {
for (var k = 0; k <= j / w[i - 1]; k++) {
dp[j] = Math.max(dp[j], dp[j - k * w[i - 1]] + k * value[i - 1]);
}
}
}
console.log(dp);
//[0, 15, 30, 45, 60]
const w = [1, 3, 4];
const value = [15, 20, 30];
const n = 4; //背包最大容量
const m = w.length; //物品的个数
let dp = new Array(n + 1).fill(0);
for (var i = 1; i <= m; i++) {
for (var j = w[i - 1]; j <= n; j++) {
dp[j] = Math.max(dp[j], dp[j - w[i - 1]] + value[i - 1]);
}
}
console.log(dp);
//[0, 15, 30, 45, 60]
第二种写法注意要点：
- 内层循环变为正向遍历
- 递推方程式与01完全背包一致
LeetCode中 “完全背包” 题型汇总：
总结：
求装满背包有几种方法，递归公式都是一样的，递推公式一般为：
dp[j] += dp[j - nums[i]];但关键在于遍历顺序不同！
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
以下标黄题目思路基本一致：
