动态规划（js版）

1. 动态规划算法介绍

理解动态规划 ~ 知乎好文

LeetCode简单的动态规划题：

• 斐波那契数
• 爬楼梯
• 使用最小花费爬楼梯【有点小坑】
• 不同路径
• 不同路径 II 【注意初始值的设置】
• 最小路径和

LeetCode较难的动态规划题：

• 343. 整数拆分
• 96. 不同的二叉搜索树

总结：

动态规划与其说是一个算法，不如说是一种方法论。
该方法论主要致力于将“合适”的问题拆分成三个子目标一一击破：

• 1.建立状态转移方程
• 2.缓存并复用以往结果
• 3.按顺序从小往大算

2. “01背包”问题

概念：有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} = 15003. 假如有吉他/音响/电脑, 验证公式:v[3][4] (1). i = 3；j = 4(2). w[i] = w[3] =3  j = 4j = 4 >= w[i] = 3 => 4 >= 3v[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 ]

注意要点：

1. 内层循环倒序遍历（且注意判断条件：j >= w[i - 1]）

原因：倒叙遍历是为了保证物品 i 只被放入一次！一旦正序遍历了，那么物品就会被重复加入多次！

2. 为何能变为一维数组

原因：实际上是把dp[i - 1]那一层拷贝到dp[i]上。

LeetCode中 “01背包” 题型汇总：

• 分割等和子集：转化后为0-1背包可行性问题。
• 目标和：转化问题以后为0-1背包方案数问题。
• 最后一块石头的重量 II：转化后为0-1背包最小值问题。
• 474. 一和零：两个维度的01背包

3. “完全背包”问题

概念：有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中 “完全背包” 题型汇总：

• 零钱兑换II

• 组合总和 Ⅳ

• 爬楼梯（进阶版）

• 零钱兑换

• 完全平方数

• 单词拆分

总结：

求装满背包有几种方法，递归公式都是一样的，递推公式一般为：dp[j] += dp[j - nums[i]]; 但关键在于遍历顺序不同！

• 如果求组合数就是外层for循环遍历物品，内层for遍历背包。

• 如果求排列数就是外层for遍历背包，内层for循环遍历物品。

4. “打家劫舍”系列

• 打家劫舍【初始值加个0】
• 打家劫舍 II【分为两个数组】
• 打家劫舍 III【树形动态规划】

5. “股票”系列【大多可用“贪心”思维】

• 买卖股票的最佳时机
• 买卖股票的最佳时机 II
• 买卖股票的最佳时机III
• 买卖股票的最佳时机IV
• 最佳买卖股票时机含冷冻期
• 买卖股票的最佳时机含手续费
  

6. “子序列”系列

• 最大子序和
• 最长连续递增序列
• 最长递增子序列【较难】
• 最长递增子序列的个数 【难】

以下标黄题目思路基本一致：

• 最长重复子数组【较难】

• 最长公共子序列【较难】

• 不相交的线【较难】

• 判断子序列

• 两个字符串的删除操作

• 不同的子序列【困难】

• 编辑距离【困难】

• 回文子串【较难】

• 最长回文子串【较难】

• 最长回文子序列

7. “跳跃游戏”系列【可用“贪心”思维】

• 55. 跳跃游戏
• 45. 跳跃游戏 II

户口查询网