八、动态规划-算法总结

八、动态规划

8.1 背景

120. 三角形最小路径和

8.1.1 DFS

// method1: 基于深度优先搜索会超时
class Solution {public int minimumTotal(List<List<Integer>> triangle) {return dfs(0, 0, triangle);}private int dfs(int x, int y, List<List<Integer>> triangle){if(x + 1 == triangle.size()){return triangle.get(x).get(y);}int leftMin = dfs(x+1, y, triangle);int rightMin = dfs(x+1, y+1, triangle);return Math.min(leftMin, rightMin) + triangle.get(x).get(y);}
}

8.1.2 DFS的优化

优化 DFS，缓存已经被计算的值（称为：记忆化搜索 本质上：动态规划）

// method2: 基于深度优先搜索 + 数据缓存 会超时
class Solution {public int minimumTotal(List<List<Integer>> triangle) {int[][] saves = new int[triangle.size()][triangle.size()];return dfs(0, 0, triangle, saves);}private int dfs(int x, int y, List<List<Integer>> triangle, int[][] saves){if(x + 1 == triangle.size()){return triangle.get(x).get(y);}// 返回计算的值if(saves[x][y] != 0){ // 已经计算过return saves[x][y];}int leftMin = dfs(x+1, y, triangle, saves);int rightMin = dfs(x+1, y+1, triangle, saves);int curMin = Math.min(leftMin, rightMin) + triangle.get(x).get(y);// 缓存当前的值saves[x][y] = curMin;return curMin;}
}

8.1.3 从DFS到动态规划

动态规划就是把大问题变成小问题，并解决了小问题重复计算的方法称为动态规划
动态规划和DFS区别

• 二叉树 子问题是没有交际，所以大部分二叉树都用递归或者分治法，即DFS，就可以解决
• 像 triangle 这种是有重复走的情况，子问题是有交际，所以可以用动态规划来解决
  自底向上

// method3: 基于动态规划
// method3-1 自底向上
class Solution {public int minimumTotal(List<List<Integer>> triangle) {// 定义保存以当前结点作为根节点向下的最小路径和int[][] dp = new int[triangle.size()][triangle.size()];// 初始化最后一层for(int i = 0;i<triangle.size();i++){dp[triangle.size()-1][i] = triangle.get(triangle.size()-1).get(i);}// 从倒数第二层向上进行dp求解for(int i = triangle.size()-2;i>=0;i--){for(int j = 0;j < triangle.get(i).size();j++){// 求解以当前结点作为根节点向下的最小路径和dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + triangle.get(i).get(j);}}return dp[0][0];}}

自顶向下

// method3: 基于动态规划
// method3-2 自顶向下
class Solution {public int minimumTotal(List<List<Integer>> triangle) {// 定义保存以当前结点作为根节点向下的最小路径和int[][] dp = new int[triangle.size()][triangle.size()];// 初始化dp[0][0] = triangle.get(0).get(0);// 从第二层依次向下进行dp求解for(int i = 1; i<triangle.size();i++){for(int j = 0;j < triangle.get(i).size();j++){// 分三种情况// s1: 当前为左边界值，只能与上一层的第一个元素相连// s2: 当前为右边界值，只能与上一层的最后一个元素相连// s3: 其余的值可以被上层的左、右两个元素相连if(j == 0){dp[i][j] = dp[i-1][0] + triangle.get(i).get(j);}else if(j == triangle.get(i).size()-1){dp[i][j] = dp[i-1][j-1] + triangle.get(i).get(j);}else{dp[i][j] = Math.min(dp[i-1][j-1],dp[i-1][j]) + triangle.get(i).get(j);}}}int min = dp[dp.length-1][0];for(int i = 0;i<dp.length;i++){min = Math.min(min, dp[dp.length-1][i]);}return min;}}

空间优化

// method3: 基于动态规划
// method3-3 自底向上(优化dp空间)
class Solution {public int minimumTotal(List<List<Integer>> triangle) {// 定义保存以当前结点作为根节点向下的最小路径和int[] dp = new int[triangle.size()];// 初始化最后一层for(int i = 0;i<triangle.size();i++){dp[i] = triangle.get(triangle.size()-1).get(i);}// 从倒数第二层向上进行dp求解for(int i = triangle.size()-2;i>=0;i--){for(int j = 0;j < triangle.get(i).size();j++){// 求解以当前结点作为根节点向下的最小路径和dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);}}return dp[0];}}

除此之外，也可以覆盖原有数据以实现空间复用。

8.2 使用场景

满足两个条件

• 满足以下条件之一
  • 求最大/最小值（Maximum/Minimun）
  • 求是否可行（Yes/No）
  • 求可行个数（Count(*)）
• 满足不能排序或者交换（Can not sort / swap）
  如题：128. 最长连续序列 位置可以交换，所以不用动态规划

8.3 四点要素

1. 状态 State
   • 灵感，创造力，存储小规模问题的结果
2. 方程 Function
   • 状态之间的联系，怎么通过小的状态，来算大的状态
3. 初始化 Intialization
   • 最极限的小状态是什么，起点
4. 答案 Answer
   • 最大的那个状态是什么，终点

常见四种类型

1. Matrix DP (10%)
2. Sequence (40%)
3. Two Sequences DP (40%)
4. Backpack (10%)
   注意点
   • 贪心算法大多题目靠背答案，所以如果能用动态规划就尽量用 DP ，不用贪心算法

8.4 矩阵类型

8.4.1 最小路径和

64. 最小路径和

// 使用 DP 解答
class Solution {public int minPathSum(int[][] grid) {// 定义保存状态的DP数组。其含义为从 grid[0][0] 当前位置的最小路径和 int[] dp = new int[grid[0].length];// 转移方程（当前元素的左边与上边路径和最小）+ 当前元素// dp = Math.min(dp[i-1], dp[i]) + grid[i][j]// 初始化// 初始化第一行由于没有上边的路径和则 dp = dp[i-1] + grid[i]for(int i = 0;i < dp.length;i++){if(i == 0){dp[i] = grid[0][i];continue;}dp[i] = dp[i-1] + grid[0][i];}// 求解答案（遍历（除第一行的）每行元素求解 DP）for(int i = 1;i < grid.length;i++){for(int j = 0;j < grid[i].length;j++){if(j == 0){ // 每行第一个元素均只能从上边的路径走来dp[j] = dp[j] + grid[i][j];continue;}dp[j] = Math.min(dp[j-1],dp[j]) + grid[i][j];}}return dp[dp.length-1];}
}

// 进阶：无需额外的 DP 空间，直接在原数组中进行 DP 解答
class Solution {public int minPathSum(int[][] grid) {// 路径只能从左上至右下（即当前结点只能从其上面一个位置或左边一个位置来）// 依次遍历行元素求解 DP （无需额外的 DP 空间，直接在原空间中求解）int i = 0, j = 0;for(i = 0;i < grid.length;i++){for(j = 0;j < grid[i].length;j++){if(i == 0 && j == 0){grid[i][j] = grid[i][j]; // 起点位置}else if(i == 0 && j != 0){grid[i][j] = grid[i][j-1] + grid[i][j]; // 上边界(非起点)}else if(i != 0 && j == 0){grid[i][j] = grid[i-1][j] + grid[i][j]; // 左边界(非起点)}else{grid[i][j] = Math.min(grid[i-1][j],grid[i][j-1]) + grid[i][j]; // 依次求解其上一个最短路径到此节点的路径}}}return grid[i-1][j-1];}
}

8.4.2 不同路径

62. 不同路径

// 基于 DP 四要素
class Solution {public int uniquePaths(int m, int n) {// 初始化状态 DP 保存从 (0, 0) 到各位置的路径总数int[] dp = new int[n];// 转移方程(上边+左边)// dp[i] = dp[i-1] + dp[i]// 初始化// 初始化第一行全为1for(int i = 0;i < dp.length; i++){dp[i] = 1;}// 求解答案for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){ // 位于左边界的解均为1dp[j] = dp[j-1] + dp[j];}}return dp[dp.length - 1];}
}

8.4.3 不同路径 II

63. 不同路径 II

// 基于 DP 四要素
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {// 定义状态 dp 保存(0, 0)到当前位置的路径数int[] dp = new int[obstacleGrid[0].length];// 转换方程// dp[i] = dp[i-1] + dp[i]// 初始化for(int i = 0; i< dp.length; i++){if(obstacleGrid[0][i] == 1){dp[i] = 0;}else{if(i == 0){dp[i] = 1; // 起始点，非阻塞则设置为1}else{dp[i] = dp[i-1] == 1?1:0; // 右边的位置依赖与左边位置的路径数}}}// 求解for(int i = 1; i < obstacleGrid.length; i++){for(int j = 0; j < obstacleGrid[i].length; j++){// 定义 dp[j] 为-1表示阻塞// 位于左边界if(j == 0){if(obstacleGrid[i][j] == 1){dp[j] = 0; // 定义当前位置阻塞}// dp[j] = d[j] 上边的路径数保留了下来continue;}// 其他位置（阻塞条件：其数为1 (or 左边、上边的路径数均为0)）if(obstacleGrid[i][j] == 1){dp[j] = 0;}else{dp[j] = dp[j-1] + dp[j];}}}return dp[dp.length-1];}
}

// 基于 DP 在无需额外的 DP 空间，直接在原数组中更新状态
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int i=0, j=0;for(i = 0; i< obstacleGrid.length;i++){for(j = 0; j < obstacleGrid[i].length; j++){if(obstacleGrid[i][j] == 1){ // 阻塞obstacleGrid[i][j] = 0; // 表示路径数为 0continue;}// 非阻塞if(i == 0 && j == 0){ // 起始点obstacleGrid[i][j] = 1;}else if(i == 0){ // 上边界（非起始点）obstacleGrid[i][j] = (obstacleGrid[i][j-1] == 1 ? 1:0); // 右边依赖左边}else if(j == 0){ // 左边界（非起始点）obstacleGrid[i][j] = (obstacleGrid[i-1][j] == 1 ? 1:0); // 下边依赖上边}else{ // 其他位置obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1];}}}return obstacleGrid[i-1][j-1];}
}

8.5 序列类型

8.5.1 爬楼梯

70. 爬楼梯

class Solution {public int climbStairs(int n) {if(n < 2){return 1;}// 斐波拉契数列// f(0) = 1, f(1) = 1, ... , f(n) = f(n-1) + f(n-2)// 状态（当前值只与前两个值有关）// 初始化（f(0) = 1, f(1) = 1）// 转换方程 f(n) = f(n-1) + f(n-2)int dp0 = 1, dp1 = 1;// 求解答案int dp2 = 0;for(int i = 2;i <= n;i++){dp2 = dp0 + dp1;dp0 = dp1;dp1 = dp2;}return dp2;}
}

8.5.2 最长递增子序列

300. 最长递增子序列

// method1：动态规划
class Solution {public int lengthOfLIS(int[] nums) {// 状态：保存以当前下标对应数字作结尾的最长递增子序列长度int[] dp = new int[nums.length];// 转移方程// 遍历 j ∈ [0, i)// dp[i] = Math.max(dp[i], dp[j]+1)// 初始化（默认各数字均有一个单元素的子序列）Arrays.fill(dp, 1);// 求解int res = 0;for(int i = 0; i< nums.length;i++){for(int j = 0;j < i;j++){if(nums[i] > nums[j]){ // 需满足前面的尾元素小于当前元素，才能构成新的递增序列dp[i] = Math.max(dp[i], dp[j] + 1);}}res = Math.max(dp[i], res); // 记录最长递增子序列长度}return res;}
}

// method2：动态规划 + 二分查找
class Solution {public int lengthOfLIS(int[] nums) {// 状态：保存以 当前下标+1 为长度的最小尾元素值// tails 是严格递增的int[] tails = new int[nums.length];// 保存最长的子序列长度int res = 0;for(int num:nums){int left = 0, right = res-1;// 基于二分查找，找寻当前数字存放与tails的空间位置// 若位于tails中间则替换原位置较大的值使尾元素最小int pos = -1;while(left<=right){int mid = left + (right - left) / 2;if(num == tails[mid]){pos = mid;break;}else if(num > tails[mid]){left = mid+1;}else{right = mid-1;}}// 有当前值则直接跳过if(pos != -1){continue;}// 写入新值（新增或覆盖）tails[right+1] = num;// 若是新增则递增resif(right+1 == res){res++;}}return res;}
}

8.5.3 单词拆分

139. 单词拆分

// method1: 从当前字符向前进行字典匹配
class Solution {public boolean wordBreak(String s, List<String> wordDict) {// 状态值：以当前字符结尾的连续字符是否存在于字典中boolean[] dp = new boolean[s.length()+1];// 初始化：空串dp[0] = true;for(int i = 1;i<=s.length();i++){for(int j = 0;j < i;j++){// 递推：从i处向前遍历，s[0,j)可以分解且s[j,i)也在集合内// 条件一：[0, j)可分解// 条件二：[j,i)在字典中if(dp[j] && wordDict.contains(s.substring(j,i))){dp[i] = true;break;}}}return dp[s.length()];}
}

// method2: 从当前字符向前进行字典匹配（加上字符最大长度限制）
class Solution {public boolean wordBreak(String s, List<String> wordDict) {// 状态值：以当前字符结尾的连续字符是否存在于字典中boolean[] dp = new boolean[s.length()+1];// 初始化：空串dp[0] = true;int maxLength = 0;for(String word:wordDict){maxLength = Math.max(maxLength, word.length());}for(int i = 1;i<=s.length();i++){// 分解的子串s[j,i)长度不会超过maxLength，注意不能越界for(int j = Math.max(0, i-maxLength);j < i;j++){// 递推：从i处向前遍历，s[0,j)可以分解且s[j,i)也在集合内// 条件一：[0, j)可分解// 条件二：[j,i)在字典中if(dp[j] && wordDict.contains(s.substring(j,i))){dp[i] = true;break;}}}return dp[s.length()];}
}

// method3: 从当前字符向后进行字典匹配
class Solution {public boolean wordBreak(String s, List<String> wordDict) {int length = s.length();// 状态值：以当前字符结尾的连续字符是否存在于字典中boolean[] dp = new boolean[length + 1];// 初始化：空串dp[0] = true;for (int i = 0; i < length; i++) {if (!dp[i]) {continue;}// i指向当前子串起始位置的前面一个位置// 计算 (i, i+someNum) 内是否存在字典中的串for (String word : wordDict) {// 条件一：之后的匹配字符不能超出字符串全长// 条件二：搜索字典中字符是否匹配if (word.length() + i <= s.length() && s.startsWith(word, i)) {dp[i + word.length()] = true;}}}return dp[length];}
}

小结

常见处理方式是给 0 位置占位，这样处理问题时一视同仁，初始化则在原来基础上length+1 ，返回结果 f[n]

• 状态可以为前 i 个
• 初始化 length + 1
• 取值 index = i - 1
• 返回值 f[n] 或者 f[m][n]

8.6 双序列类型

8.6.1 最长公共子序列

1143. 最长公共子序列

class Solution {public int longestCommonSubsequence(String text1, String text2) {// 状态：二维矩阵 dp[i][j] 保存 text1[0,i-1] 与 text2[0,j-1] 的最长公共子序列的长度int m = text1.length();int n = text2.length();int[][] dp = new int[m+1][n+1];// 状态转移方程// ① text1[i - 1] == text2[j - 1] 意味着在前一长度下新增一个长度，则 dp[i][j] = d[i-1][j-1] + 1// ② text1[i - 1] != text2[j - 1] 意味着双方新增的字符不等，则比较一方新增字符另一方不新增字符情况下的最大长度值// dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])// 初始化// i = 0, j = 0 意味着是空串匹配，均初始化为 0（java数组默认行为, 此处不做）// 求解for(int i = 1; i <= m;i++){for(int j = 1; j<=n; j++){if(text1.charAt(i-1) == text2.charAt(j-1)){dp[i][j] = dp[i-1][j-1] + 1;}else{dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);}}}return dp[m][n];}
}

注意点

• 从 1 开始遍历到最大长度
• 索引需要减一

8.6.2 编辑距离

class Solution {public int minDistance(String word1, String word2) {// 状态：记录 word1[0, i-1] 到 word2[0, i-1] 最少操作次数int m = word1.length();int n = word2.length();int[][] dp = new int[m+1][n+1];// 初始化// i = 0 or j = 0 表示存在某一个单词为空，则需要执行另一个单词个数的删除（新增）操作for(int i = 1;i <= m;i++){dp[i][0] = i;}for(int i = 1;i <= n;i++){dp[0][i] = i;}// 状态转换方程// ① word1[i - 1] == word2[j - 1] 则不操作，dp[i][j] = dp[i-1][j-1]// ② word1[i - 1] != word2[j - 1] 则最小操作数 dp[i][j] = Min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1for(int i = 1;i<=m;i++){for(int j = 1;j<=n;j++){if(word1.charAt(i-1) == word2.charAt(j-1)){dp[i][j] = dp[i-1][j-1];}else{dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]), dp[i-1][j-1]) + 1;}}}return dp[m][n];}
}

8.7 零钱和背包

8.7.1 零钱兑换

322. 零钱兑换

class Solution {public int coinChange(int[] coins, int amount) {// 定义状态：dp[i] 表示总金额为i时需要的最少的硬币数int[] dp = new int[amount+1];// 初始化dp[0] 表示总金额为0时最少的硬币数为0dp[0] = 0;for(int i = 1;i<=amount;i++){// 记录当前总金额下所需要的最少的硬币数int minCount = Integer.MAX_VALUE;for(int c:coins){// 若以当前硬币作为最后一次加入if(i - c >= 0){if(dp[i-c] == -1){ // 之前的总金额的最少硬币数不存在（即不能凑出i-c）dp[i] = -1; // 设置以当前硬币添加作为最后一次加入的方法不能组成总金额}else{minCount = Math.min(minCount, dp[i-c]+1); // 记录最小的硬币个数}}}// 若没有做比较则不存在硬币组合方法dp[i] = (minCount == Integer.MAX_VALUE?-1:minCount);}return dp[amount];}
}

8.7.2 零钱兑换 II

518. 零钱兑换 II
先遍历物品再遍历背包 - 组合数
先遍历背包再遍历物品 - 排列数

class Solution {public int change(int amount, int[] coins) {// 状态：dp[i] 保存 总金额为 i 的硬币组合数int[] dp = new int[amount+1];// 初始化：dp[0] 表示总金额为0时 硬币组合数为1dp[0] = 1;// 组合先遍历零钱，再遍历总额// 排列先遍历总额，再遍历零钱for(int c:coins){for(int i = c;i<=amount;i++){dp[i] += dp[i-c];}}return dp[amount];}
}

8.7.3 分割等和子集

416. 分割等和子集

// 基于二维数组
class Solution {public boolean canPartition(int[] nums) {// 累加 nums 的各元素int sum = 0;for(int n:nums){sum+=n;}// 如果不能平分则返回falseif(sum % 2 != 0){return false;}// 问题转换为在集合中能否找到总和等于sum/2的子集// 状态：当前行以及以前的所有数字类别组合能刚好等于当前下标值boolean[][] dp = new boolean[nums.length+1][sum/2+1];for(int i = 1;i <= nums.length;i++){for(int j = 1;j <= sum/2;j++){if(j - nums[i-1] > 0){ // 可以装入当前物品后装入其他物品dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];}else if(j - nums[i-1] < 0){ // 当前物品放不下dp[i][j] = dp[i-1][j];}else{ // 刚好放下dp[i][j] = true;}}}return dp[nums.length][sum/2];}
}

// 一维数组
class Solution {public boolean canPartition(int[] nums) {// 累加 nums 的各元素int sum = 0;for(int n:nums){sum+=n;}// 如果不能平分则返回falseif(sum % 2 != 0){return false;}// 问题转换为在集合中能否找到总和等于sum/2的子集// 状态：当前行以及以前的所有数字类别组合能刚好等于当前下标值boolean[] dp = new boolean[sum/2+1];for(int i = 0;i < nums.length;i++){for(int j = sum/2;j >= 1;j--){ // 此处需要逆序遍历金额，如果升序会下一行覆盖上一行的结果if(j - nums[i] > 0){ // 可以装入当前物品后装入其他物品dp[j] = dp[j] || dp[j-nums[i]];}else if(j - nums[i] < 0){ // 当前物品放不下// dp[j] = dp[j];}else{ // 刚好放下dp[j] = true;}}}return dp[sum/2];}
}