【Java】HOT100+代码随想录：动态规划（下）

三、打家劫舍

LeetCode198：打家劫舍

LeetCode213：打家劫舍ii

LeetCode337：打家劫舍iii（树形）

四、股票问题

时间不多了，其他的先不写了

LeetCode121：买卖股票的最佳时机

五、子序列问题

5.1 子序列不连续

LeetCode300：最长递增子序列（不连续）

LeetCode1143：最长公共子序列（不连续，但有相对顺序）

LeetCode1035：不相交的线（不连续，但有相对顺序）

5.2 子序列连续

LeetCode674：最长连续递增子序列

LeetCode718：最长重复子数组（连续，无顺序）

LeetCode53：最大子序和

LeetCode2：乘积最大子数组和

5.3 编辑距离

LeetCode392：判断子序列

LeetCode115：不同的子序列

LeetCode583：两个字符串的删除操作

LeetCode72：编辑距离

5.4 回文问题

LeetCode647：回文子串

LeetCode516：最长回文子序列

三、打家劫舍

LeetCode198：打家劫舍

相邻房屋被偷报警，不触动警报装置的情况下，能偷到的最高金额

思路：当前状态和前面状态会有一种依赖关系，那么这种依赖关系都是动规的递推公式。

dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
递推公式：如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
如果不偷第i房间，那么dp[i] = dp[i - 1]，即考虑i-1房。然后dp[i]取最大值，即
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
初始化：从递推公式可以看出，递推的基础是dp[0]=nums[0]，dp[1]=max(dp[0],dp[1]))

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

LeetCode213：打家劫舍ii

思路：为了不使他成环，考虑首元素（不包含尾元素）和尾元素（不包含首元素）两种情况。

class Solution {public int rob(int[] nums) {if (nums == null || nums.length == 0)return 0;int len = nums.length;if (len == 1)return nums[0];return Math.max(robAction(nums, 0, len - 1), robAction(nums, 1, len));}int robAction(int[] nums, int start, int end) {int x = 0, y = 0, z = 0;for (int i = start; i < end; i++) {y = z;z = Math.max(y, x + nums[i]);x = y;}return z;}
}

LeetCode337：打家劫舍iii（树形）

思路：关键在于该节点是抢还是不抢。如果抢了当前节点，两个孩子就不能动，如果没抢当前节点，就可以考虑抢左右孩子（注意这里说的是“考虑”）

树形dp：返回长度为2的数组，dp数组（dp table）以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱

终止条件：遍历到空节点；遍历顺序：显然是左右中（后序遍历），因为需要处理返回值

单层递归逻辑：如果是偷当前节点，那么左右孩子就不能偷；如果不偷当前节点，那么左右孩子就都可以偷，至于到底偷不偷一定是选最大的相加

最终头结点就是取下标0 和下标1的最大值就是偷得的最大金钱。

class Solution {public int rob(TreeNode root) {int[] res = new int[2];res = robAction(root);return Math.max(res[0],res[1]);}public int[] robAction(TreeNode root){int[] res = new int[2];if(root==null)  return res;int[] left = robAction(root.left);int[] right = robAction(root.right);//不偷当前节点，偷左右孩子res[0] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);//偷当前节点，不偷左右孩子res[1] = root.val + left[0] + right[0];return res;}
}

四、股票问题

时间不多了，其他的先不写了

LeetCode121：买卖股票的最佳时机

首先贪心解法，每次在最低点购入，然后最高点抛出

class Solution {public int maxProfit(int[] prices) {// 找到一个最小的购入点int low = Integer.MAX_VALUE;// res不断更新，直到数组循环完毕int res = 0;for(int i = 0; i < prices.length; i++){low = Math.min(prices[i], low);res = Math.max(prices[i] - low, res);}return res;}
}

其次，动态规划，使用一个二维dp数组，dp[i][0]代表第i天持有股票所得现金，dp[i][1]代表不持有

● 推导公式：分为两种情况：如果第i天持有股票，则来源于两种情况：1. 第i-1天就持有股票，则所得现金不变；2. 第i天买入股票，所得现金为-prices[i]。如果第i天不持有股票，则来源于两种情况：1. 第i-1天就持有股票，则卖出股票，所得现金为prices[i]；2. 第i天不持有股票，所得现金不变

dp[i][0] = max(dp[i - 1][0], -prices[i]); 和 dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

● 初始化：第0天持有股票，则一定是买入股票：dp[0][0] = -prices[0]；第0天不持有，则dp[0][1]=0

结果就是dp[prices.length-1][1]，因为本题中不持有股票状态所得金钱一定比持有股票状态得到的多！

class Solution {public int maxProfit(int[] prices) {if (prices == null || prices.length == 0) return 0;int length = prices.length;// dp[i][0]代表第i天持有股票的最大收益// dp[i][1]代表第i天不持有股票的最大收益int[][] dp = new int[length][2];int result = 0;dp[0][0] = -prices[0];dp[0][1] = 0;for (int i = 1; i < length; i++) {dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);}return dp[length - 1][1];}
}

五、子序列问题

子序列问题是动态规划解决的经典问题，当前下标i的递增子序列长度，其实和i之前的下表j的子序列长度有关系

5.1 子序列不连续

LeetCode300：最长递增子序列（不连续）

思路：dp[i]表示以nums[i]为结尾的最长递增子序列的长度。初始化都是1。

递推公式：dp[i]等于j从0-i的最大升序列+1

class Solution {public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];int res = 1;//每个递增子序列的大小都最起码是1（因为最少包含nums[i]）Arrays.fill(dp, 1);for (int i = 1; i < dp.length; i++) {//j会遍历0-i-1的每一个值，来进行比较并更新dp[i]，因此要和dp[i]本身取最大值//每次遍历如果是递增的就+1（不用连续递增），不然就保持不变for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}//然后也是取所有dp[i]里面最长的一个子序列res = Math.max(res, dp[i]);}return res;}
}

LeetCode1143：最长公共子序列（不连续，但有相对顺序）

思路：1. dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]; 取dp[len1][len2]；2. 不同于最长重复子数组的定义：如果相等就+1，如果不相等就还是为0，在这里如果相等就+1，如果不相等，则取text1[0,i-2]和text2[0,j-1]的最长公共子序列和text1[0,i-1]和text2[0,j-2]的最大值,即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])；3. 根据定义初始化为0

class Solution {public int longestCommonSubsequence(String text1, String text2) {int[][] dp = new int[text1.length()+1][text2.length()+1];for(int i=1;i<=text1.length();i++){char char1= text1.charAt(i-1);for(int j=1;j<=text2.length();j++){char char2 = text2.charAt(j-1);if(char1 == char2){dp[i][j] = dp[i-1][j-1] +1;}else{dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);}}}return dp[text1.length()][text2.length()];}
}

一维dp：由于用pre记录了上一个值，所以不会出现重复叠加，所以第二个循环j不用倒序

class Solution {public int longestCommonSubsequence(String text1, String text2) {int[] dp = new int[text2.length()+1];for(int i=1;i<=text1.length();i++){int pre = dp[0];char char1= text1.charAt(i-1);for(int j=1;j<=text2.length();j++){int cur = dp[j];char char2 = text2.charAt(j-1);if(char1 == char2){dp[j] = pre +1;}else{dp[j] = Math.max(dp[j-1], dp[j]);}pre = cur;}}return dp[text2.length()];}
}

LeetCode1035：不相交的线（不连续，但有相对顺序）

思路：其实问有几条不相交的线，就是在字符串A中找到一个和字符串B相同的子序列（不能改变相对顺序），求子序列的长度。

本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！

基本上copy上一题代码即可ac

class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int[][] dp = new int[nums1.length+1][nums2.length+1];for(int i=1;i<=nums1.length;i++){for(int j=1;j<=nums2.length;j++){if(nums1[i-1] == nums2[j-1]){dp[i][j] = dp[i-1][j-1] +1;}else{dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);}}}return dp[nums1.length][nums2.length];}
}

5.2 子序列连续

LeetCode674：最长连续递增子序列

思路：因为本题要求连续递增子序列，所以就只要比较nums[i]与nums[i - 1]，而不用去比较nums[j]与nums[i] （j是在0到i之间遍历）。既然不用j了，那么也不用两层for循环，本题一层for循环就行，比较nums[i] 和 nums[i - 1]。

class Solution {public int findLengthOfLCIS(int[] nums) {int[] dp = new int[nums.length];int res = 1;//每个递增子序列的大小都最起码是1（因为最少包含nums[i]）Arrays.fill(dp, 1);for (int i = 1; i < dp.length; i++) {if(nums[i] > nums[i-1]){dp[i] = dp[i-1] +1;}//然后也是取所有dp[i]里面最长的一个子序列res = Math.max(res, dp[i]);}return res;}
}

LeetCode718：最长重复子数组（连续，无顺序）

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。取最大res。

题目中说子数组，其实就是连续子序列。

思路：二维dp。动规五部曲——1. dp[i][j]代表以i-1为结尾的A和以j-1为结尾的B的最长重复子数组的长度，记得数组的大小为nums.length+1（因为是从1开始的）；2. 递推公式：当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1;根据递推公式可以看出，遍历i 和 j 要从1开始！；3. 初始化：举例dp[1][1]=dp[0][0]+1，则dp[0][0]=0才能进行接下来的推导；4. 遍历顺序和举例推导省略不提

为什么使用i-1下标作为判断，而不使用i下标呢？这是由于使用i-1，可以直接从下标1开始进行判断，更新dp数组，而如果使用i，就需要考虑到下标0的A和下标i的B相等的情况，需要先对第一行/第一列进行初始化后再进行for循环，多了一些步骤，不够简洁

class Solution {public int findLength(int[] nums1, int[] nums2) {int res = 0;int[][] dp = new int[nums1.length+1][nums2.length+1];for(int i=1;i<nums1.length+1;i++){for(int j=1;j<nums2.length+1;j++){if(nums1[i-1] == nums2[j-1]){dp[i][j] = dp[i-1][j-1] + 1;res = Math.max(res, dp[i][j]);}}}return res;}
}

一维dp（滚动数组）重点在于：不相等的时候记得给dp[j]赋0

class Solution {public int findLength(int[] nums1, int[] nums2) {int res = 0;int[] dp = new int[nums2.length+1];for(int i=1;i<nums1.length+1;i++){for(int j=nums2.length;j>0;j--){if(nums1[i-1] == nums2[j-1]){dp[j] = dp[j-1] + 1;}else{  //当不相等时说明没有以i-1和j-1为最后一个元素的最长公共子数组，所以为0dp[j] = 0;}res = Math.max(res, dp[j]);}}return res;}
}

LeetCode53：最大子序和

思路：贪心的思路就是如果当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

照例，我们通过动规五部曲来分析一下

dp定义：dp[i]即包含nums[i]的最大子序和；

递推公式：dp[i]来源于两个方向：一个是dp[i-1]+nums[i]，nums[i]加入当前子序和；另一个是放弃之前的子序和，重新开始计算连续子序和。dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])；也可以写成dp[i] = dp[i - 1]<0? nums[i] :dp[i-1] + nums[i];

初始化：dp[0]=nums[0]

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

类似的，

LeetCode2：乘积最大子数组和

class Solution {public int maxProduct(int[] nums) {int[] dp = new int[nums.length];  //0-i个数，获得最大的成绩int res = nums[0];dp[0] = nums[0];for(int i=1; i<nums.length;i++){dp[i] = Math.max(dp[i-1]*nums[i], nums[i]);res = Math.max(res, dp[i]);}return res;}
}

5.3 编辑距离

LeetCode392：判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

思路：类似1143 最长公共子序列，区别在于1143是s、t都可以删去元素，本题只删去字符串t里的

dp[i][j]指的是以i-1为结尾的字符串s和j-1为结尾的字符串t的相同子序列长度；

如果s[i-1] = t[j-1]，则长度+1——dp[i][j] = dp[i - 1][j - 1] + 1;

如果不相等，相当于删去t[j-1]，就长度不变——dp[i][j] = dp[i][j - 1]；

是否是子序列，即dp[len1][len2] 是否== len1

class Solution {public boolean isSubsequence(String s, String t) {int length1 = s.length(); int length2 = t.length();int[][] dp = new int[length1+1][length2+1];for(int i = 1; i <= length1; i++){for(int j = 1; j <= length2; j++){if(s.charAt(i-1) == t.charAt(j-1)){dp[i][j] = dp[i-1][j-1] + 1;}else{dp[i][j] = dp[i][j-1];}}}if(dp[length1][length2] == length1){return true;}else{return false;}}
}

//压缩成一维dp
class Solution {public boolean isSubsequence(String s, String t) {int[] dp = new int[s.length() + 1];for (int i = 1; i <= t.length(); i ++) {// 需要使用上一轮的dp[j - 1]，所以使用倒序遍历for (int j = s.length(); j > 0; j --) {if (t.charAt(i-1) == s.charAt(j - 1)) {dp[j] = dp[j - 1] + 1;}}}return dp[s.length()] == s.length();}
}

LeetCode115：不同的子序列

思路：我们求的是 s 中有多少个 t，而不是求t中有多少个s，所以只考虑 s中删除元素的情况，即不用s[i - 1]来匹配的情况。相当于s中删除元素得到t有多少种方案

dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。

递推公式：

class Solution {public int numDistinct(String s, String t) {//以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]int[][] dp = new int[s.length() + 1][t.length() + 1];//初始化：dp[i][0]——以i-1为结尾的s可以随便删除元素，出现空字符串的方案个数=1（删除全部元素）//dp[0][j]：空字符串s可以随便删除元素，出现以j-1为结尾的字符串t的个数=0for (int i = 0; i < s.length() + 1; i++) {dp[i][0] = 1;}for (int i = 1; i < s.length() + 1; i++) {for (int j = 1; j < t.length() + 1; j++) {//相等，包括用s[i-1]来匹配和不用s[i-1]来匹配已经存在的方案个数if (s.charAt(i - 1) == t.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];}else{    //不相等，删除s字符串中的s[i-1]dp[i][j] = dp[i - 1][j];}}}return dp[s.length()][t.length()];}
}

LeetCode583：两个字符串的删除操作

找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

思路1：相比于115，两个字符串都可以删除

dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。

递推：当word1[i - 1] = word2[j - 1]时，继承上一个循环的dp不变——dp[i][j] = dp[i - 1][j - 1];

当word1[i - 1] 不等于 word2[j - 1]时，包含三种情况，删除word1[i-1]，删除word2[j - 1]和同时删word1[i - 1]和word2[j - 1]，即dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

因为 dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2，所以递推公式可简化为：dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);（只需考虑这两种情况）

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

思路2：只要求出两个字符串的最长公共子序列长度即可，那么除了最长公共子序列之外的字符都是必须删除的

lass Solution {public int minDistance(String word1, String word2) {int len1 = word1.length();int len2 = word2.length();int[][] dp = new int[len1 + 1][len2 + 1];for (int i = 1; i <= len1; i++) {for (int j = 1; j <= len2; j++) {if (word1.charAt(i - 1) == word2.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 len1 + len2 - dp[len1][len2] * 2;}
}

LeetCode72：编辑距离

可以插入、删除、替换一个字符，计算出将 word1 转换成 word2 所使用的最少操作数。

思路：dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。

递推公式：

if (word1[i - 1] == word2[j - 1])不操作    dp[i][j] = dp[i - 1][j - 1];
if (word1[i - 1] != word2[j - 1])增    word2加一个相当于word1减一个删    word1删一个：dp[i][j] = dp[i - 1][j] + 1;word2删一个：dp[i][j] = dp[i][j - 1] + 1;换    dp[i][j] = dp[i - 1][j - 1] + 1;所以总结就是 dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;选操作步骤最少的一个

初始化：

dp[i][0] ：以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0]。

那么dp[i][0]就应该是i，对word1里的元素全部做删除操作，即：dp[i][0] = i;同理dp[0][j] = j;

for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;

代码：

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=0;i<=m;i++)   dp[i][0] = i;for(int j=0;j<=n;j++)   dp[0][j] = j;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][j-1], dp[i-1][j])) + 1;}}}return dp[m][n];}
}

5.4 回文问题

LeetCode647：回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

思路：如何递推呢？我们在判断字符串S是否是回文，那么如果我们知道 s[1]，s[2]，s[3] 这个子串是回文的，那么只需要比较 s[0]和s[4]这两个元素是否相同，如果相同的话，这个字符串s 就是回文串。

所以定义bool类型的dp数组，表示[i,j]子串是否是回文串

当s[i]!=s[j]时 dp[i][j] = false;

s[i]==s[j]时，是否是回文串要看子串的大小（即i、j的差值）1. 如果相同则true 2. 如果相差一也是。如果相差大于1，则需要判断dp[i+1][j-1]是否是回文串。

if (s[i] == s[j]) {if (j - i <= 1) { // 情况一 和 情况二result++;dp[i][j] = true;} else if (dp[i + 1][j - 1]) { // 情况三result++;dp[i][j] = true;}
}

初始化为false，遍历顺序从下到上，从左到右

class Solution {public int countSubstrings(String s) {char[] chars = s.toCharArray();int len = chars.length;boolean[][] dp = new boolean[len][len];int result = 0;for (int i = len - 1; i >= 0; i--) {for (int j = i; j < len; j++) {if (chars[i] == chars[j]) {if (j - i <= 1) { // 情况一 和 情况二result++;dp[i][j] = true;} else if (dp[i + 1][j - 1]) { //情况三result++;dp[i][j] = true;}}}}return result;}
}

LeetCode516：最长回文子序列

思路：注意区分回文子串和回文子序列，回文子串是要连续的，回文子序列可不是连续的！

dp[i][j]：【i,j】范围内的最长回文子串

递推：如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入并不能增加[i,j]区间回文子序列的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);（可以看出遍历还是从下到上，从左到右）

初始化：dp[i][i] = 1；

public class Solution {public int longestPalindromeSubseq(String s) {int len = s.length();int[][] dp = new int[len + 1][len + 1];for (int i = len - 1; i >= 0; i--) { // 从后往前遍历 保证情况不漏dp[i][i] = 1; // 初始化for (int j = i + 1; j < len; j++) {if (s.charAt(i) == s.charAt(j)) {dp[i][j] = dp[i + 1][j - 1] + 2;} else {dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);}}}return dp[0][len - 1];}
}