秋招力扣Hot100刷题总结——动态规划

一、01背包

01背包问题中，遍历顺序可以是先物品后背包，也可以是先背包后物品，但是背包要倒序遍历。

1. 等和子集

• 题目要求：给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
• 代码及思路：
  • dp数组表示容量为j的背包装的最大和
  • 递推公式为：dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i])

class Solution {public boolean canPartition(int[] nums) {int sum=0;for(int i=0;i<nums.length;i++){sum+=nums[i];}if(sum%2!=0)return false;sum=sum/2;int[] dp=new int[sum+1];for(int i=0;i<nums.length;i++){for(int j=sum;j>=nums[i];j--){dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);}}return dp[sum]==sum;}
}

二、完全背包（物品可以重复使用）

完全背包问题中，先遍历物品再遍历背包，且背包正序变历。

1. 完全平方数

• 题目要求：给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
  
• 代码及思路
  • 使用动态规划解决问题
  • dp数组的含义是和为整数n的最小平方数
  • dp的初始化：dp[1]为1，后面的都初始化为Integer.MAX_VALUE，因为要求最小值
  • 状态转移公式：dp[j]=Math.min(dp[j],dp[j-ii]+1);
    注：一定要判断dp[j-ii]!=Integer.MAX_VALUE，否则会出错
  • 代码

class Solution {public int numSquares(int n) {int[] dp=new int[n+1];dp[1]=1;dp[0]=0;for(int i=2;i<=n;i++){dp[i]=Integer.MAX_VALUE;}for(int i=1;i<=n/2;i++){for(int j=i*i;j<=n;j++){if(dp[j-i*i]!=Integer.MAX_VALUE){dp[j]=Math.min(dp[j],dp[j-i*i]+1);}}}return dp[n];}
}

2. 零钱兑换 题目链接

• 题目要求：给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
  计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
  你可以认为每种硬币的数量是无限的。
  
• 代码及思路
  • dp数组定义为总金额为j时的最少硬币数
  • 初始化：将dp数组的值初始化为Integer.MAX_VALUE，但是dp[0]必须初始化为0
  • 遍历顺序：外层物品内层背包，都是正序遍历
  • 状态转移矩阵：if(dp[j-coins[i]]!=Integer.MAX_VALUE){
    dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);
    }
  • 最后判断总金额为amount时，硬币个数是否是Integer.MAX_VALUE
  • 代码

class Solution {public int coinChange(int[] coins, int amount) {int[] dp=new int[amount+1];for(int i=0;i<=amount;i++){dp[i]=Integer.MAX_VALUE;}dp[0]=0;for(int i=0;i<coins.length;i++){for(int j=coins[i];j<=amount;j++){if(dp[j-coins[i]]!=Integer.MAX_VALUE){dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);}}}if(dp[amount]==Integer.MAX_VALUE)return -1;return dp[amount];}
}

三、最大正方形、矩形面积

1. 最大正方形（中等）

• 题目要求:在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。
  
• 代码及思路
  • 使用动态规划来实现。其中dp数组表示以 (i, j) 为右下角的最大正方形的边长；
  • 初始化：第一行和第一列中，当矩阵值为1的时候，最大边长为1
  • 状态转移矩阵：dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
  • 更新最大边长
  • 代码

class Solution {public int maximalSquare(char[][] matrix) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return 0;}int m = matrix.length;int n = matrix[0].length;int maxSide = 0;// dp 数组，表示以 (i, j) 为右下角的最大正方形的边长int[][] dp = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (matrix[i][j] == '1') {if (i == 0 || j == 0) {// 如果在第一行或第一列，dp[i][j] 就是 matrix[i][j] 本身dp[i][j] = 1;} else {// 状态转移方程dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;}// 更新最大边长maxSide = Math.max(maxSide, dp[i][j]);}}}// 返回最大正方形的面积return maxSide * maxSide;}
}

2. 最大矩形（困难）

• 题目要求：给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
  
• 代码及思路
  • 使用三个数组 height、left 和 right 来记录每一行的高度，最左和最右扩展边界。
  • 然后逐行计算，以每行作为底边，利用这些数组计算每个位置的最大矩形面积。
  • 代码

public class Solution {public int maximalRectangle(char[][] matrix) {if (matrix.length == 0) {return 0;}int rows = matrix.length;int cols = matrix[0].length;int maxArea = 0;int[] height = new int[cols];int[] left = new int[cols];int[] right = new int[cols];for (int i = 0; i < cols; i++) {right[i] = cols;}for (int i = 0; i < rows; i++) {int curLeft = 0, curRight = cols;// Update heightfor (int j = 0; j < cols; j++) {if (matrix[i][j] == '1') {height[j]++;} else {height[j] = 0;}}// Update leftfor (int j = 0; j < cols; j++) {if (matrix[i][j] == '1') {left[j] = Math.max(left[j], curLeft);} else {left[j] = 0;curLeft = j + 1;}}// Update rightfor (int j = cols - 1; j >= 0; j--) {if (matrix[i][j] == '1') {right[j] = Math.min(right[j], curRight);} else {right[j] = cols;curRight = j;}}// Update maxAreafor (int j = 0; j < cols; j++) {maxArea = Math.max(maxArea, (right[j] - left[j]) * height[j]);}}return maxArea;}
}

四、编辑距离

1. 编辑距离 题目链接

• 题目描述：给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
  你可以对一个单词进行如下三种操作：
  插入一个字符
  删除一个字符
  替换一个字符
  
• 代码及思路
  • dp数组表示字符串1中下标0到i-1的子串和字符串2中下标0到j-1的子串的最小编辑距离
  • 初始化是两个字符串分别有一个是空串的编辑距离
  • 遍历顺序正序遍历，但注意是从i,j=1开始
  • 递推公式
    • 当字符串1中下标i-1的字符和 字符串2中下标j-1的字符相等时：dp[i][j]=dp[i-1][j-1];
    • 不相等时，有修改、删除和插入三种情况：dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
  • 代码

class Solution {public int minDistance(String word1, String word2) {int m=word1.length();int n=word2.length();int[][] dp=new int[m+1][n+1];for(int i=1;i<=m;i++){dp[i][0]=i;}for(int i=1;i<=n;i++){dp[0][i]=i;}for(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(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;}}}return dp[m][n];}
}

五、打家劫舍

1. 打家劫舍 III

• 题目要求：小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
  给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
  
• 代码及思路
  • 使用动态规划解决，每一个二叉树的顶点都有两种情况：偷该顶点不偷孩子；偷孩子不偷该顶点
  • 本题不能使用传统的dp数组，而是考虑二叉树的递归，每一个顶点使用一个一维数组存储其两种情况下能偷的最大值

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int rob(TreeNode root) {int[] result = robOfTwoChoice(root);return Math.max(result[0], result[1]);}private int[] robOfTwoChoice(TreeNode node){int[] result = new int[2];if(node==null)return result;// 递归计算当前节点左儿子偷与不偷所能获得的最大金额int[] left = robOfTwoChoice(node.left);// 递归计算当前节点右儿子偷与不偷所能获得的最大金额int[] right = robOfTwoChoice(node.right);// 不偷当前节点时能得到的最大金额 = 左孩子能偷到的最大金额 + 右孩子能偷到的最大金额；result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);// 偷当前节点时能得到的最大金额 = 左孩子选择不偷自己时能得到的最大金额 + 右孩子选择不偷自己时能得到的最大金额 + 当前节点的金额result[1] = left[0] + right[0] + node.val;return result;}
}

2. 打家劫舍 题目链接

class Solution {public int rob(int[] nums) {int[] dp=new int[nums.length+1];dp[0]=0;dp[1]=nums[0];for(int i=2;i<=nums.length;i++){dp[i]=Math.max(dp[i-2]+nums[i-1],dp[i-1]);}return dp[nums.length];}
}

六、字符串问题

1. 回文子串

• 题目要求：给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
  回文字符串 是正着读和倒过来读一样的字符串。
  子字符串 是字符串中的由连续字符组成的一个序列。
  
• 代码及思路
  • 使用动态规划解决，使用二维dp数组
  • dp数组表示下标为i到j之间的子字符串是否为回文数组
  • 递推公式有两种情况：当子字符串之间距离小于等于1时，直接为true；当距离大于1时，根据子字符串i+1到j-1是否为回文子串判断
  • 遍历顺序为倒序

class Solution {public int countSubstrings(String s) {int l=s.length();boolean[][] dp=new boolean[l][l];int res=0;for(int i=l-1;i>=0;i--){for(int j=i;j<l;j++){if(s.charAt(i)==s.charAt(j)){if(j-i<=1){res++;dp[i][j]=true;}else{if(dp[i+1][j-1]==true){res++;dp[i][j]=true;}}}}}return res;}
}

2. 最长回文子串

• 题目要求：给你一个字符串 s，找到 s 中最长的回文子串。
  
• 代码及思路
  • 本题dp数组表示s中下标从i到j之间的子串是否是回文子串
  • 递推公式有两种情况：当子字符串之间距离小于等于1时，直接为true；当距离大于1时，根据子字符串i+1到j-1是否为回文子串判断
  • 遍历顺序是外层循环倒序，内层循环正序
  • 代码

class Solution {public String longestPalindrome(String s) {boolean[][] dp=new boolean[s.length()][s.length()];int l=s.length();String res="";dp[0][0]=true;for(int i=l-1;i>=0;i--){for(int j=i;j<l;j++){if(s.charAt(i)==s.charAt(j)){if(j-i<=1||dp[i+1][j-1]){dp[i][j]=true;if(res.length()<s.substring(i,j+1).length()){res=s.substring(i,j+1);}}}}}return res;}
}

3. 单词拆分（完全背包） 题目链接

• 题目要求：给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
  注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
  
• 代码及思路
  • dp数组表示下标为0到i-1时的子字符串能否由字典组成
  • 初始化：dp[0]=true;一定要初始化，否则是无法正确导的
  • 遍历顺序：外层遍历字符串，内层遍历字典
  • 递推公式：if(i>=l&&dp[i-l]&&s.substring(i-l,i).equals(str)){
    dp[i]=true; }
  • 代码

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(String str:wordDict){int l=str.length();if(i>=l&&dp[i-l]&&s.substring(i-l,i).equals(str)){dp[i]=true;}}}return dp[s.length()];}
}

七、路径问题

1. 不同路径 题目链接

• 题目要求：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
  机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
  问总共有多少条不同的路径？

• 代码及思路
  • 使用动态规划解决问题，dp数组表示下标为i，j的点有几种路径
  • 初始化：因为只能向右和下移动，因此将第一行和第一列都初始化为1
  • 遍历顺序：内外循环都正序遍历
  • 状态转移：dp[i][j]=dp[i-1][j]+dp[i][j-1];
  • 代码

class Solution {public int uniquePaths(int m, int n) {int[][] dp=new int[m][n];for(int i=0;i<m;i++){dp[i][0]=1;}for(int j=-0;j<n;j++){dp[0][j]=1;}for(int i=1;i<m;i++){for(int j=1;j<n;j++){dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m-1][n-1];}
}

其他

1. 最长递增子序列

• 题目要求：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
  子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的
  子序列。
  
• 代码及思路
  • 使用动态规划解决
  • 动归数组表示从下标为0到下标为i的最长子序列
  • 遍历顺序：外层变量数组元素，内层遍历从下标0到下标i的元素
  • 状态转移矩阵：if(nums[i]>nums[j]){
    dp[i]=Math.max(dp[i],dp[j]+1);
    }
  • 每次外层遍历使用dp[i]更新最长子序列值
  • 代码

class Solution {public int lengthOfLIS(int[] nums) {int[] dp=new int[nums.length];int res=1;for(int i=0;i<nums.length;i++){dp[i]=1;}for(int i=1;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(res,dp[i]);}return res;}
}