一、动态规划基本解题技巧

学习自：https://labuladong.gitee.io/algo/3/23/71/

1.1零钱兑换（中等）

对题目做出四点分析：base case 、状态（原问题和子问题中发生变化的变量）、选择（是什么导致状态发生了变化）、dp数组的含义

回到本题中，对于某个总金额m，它凑齐它所需的最小硬币数 = min（m - 每个硬币的面额）+ 1，当然应该判断 m - 每个硬币的面额 大于等于0，否则跳过。

因为题目说了coins是无限的，所以无论什么金额，都需要依次遍历所有的coins。

class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];// 因为我们求解的是min，所以要先初始dp数组值为无穷大Arrays.fill(dp, amount + 1);// 凑成0块钱，需要0个硬币dp[0] = 0;// 从 金额 1 - amount依次求解for (int i = 1; i <= amount; i++) {// dp[i] = min(dp[i - coins[j] + 1]) (遍历所有面额 coins[j])for (int j = 0; j < coins.length; j++) {// 判断硬币面额是否超过当前金额if (coins[j] <= i) {dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);}}}return dp[amount] == amount + 1 ? -1 : dp[amount];}
}

动态规划不就是从最简单的 base case 往后推导吗，可以想象成一个链式反应，以小博大。但只有符合最优子结构的问题，才有发生这种链式反应的性质。

找最优子结构的过程，其实就是证明状态转移方程正确性的过程，方程符合最优子结构就可以写暴力解了，写出暴力解就可以看出有没有重叠子问题了，有则优化，无则 OK。这也是套路，经常刷题的朋友应该能体会。

---

二、子序列类型问题（数组+字符串）

2.1涉及两个字符串、数组的题目

2.1.1最长公共子序列（中等）（掌握模板）

注意题目要求，可删除、最长公共序列。

用dp[i][j]，记录text1[1…i] 与 text2[1…j]的最长公共子序列的长度，那么对所有的 i 而言，dp[i][0] = 0，因为text2没有包含在内的字符；对所有的 j 而言，dp[0][j] = 0。

对于dp[i][j]，相比于dp[i - 1][j - 1]，text1和text2都增加了一个字符，所以，如果text1[i] == text2[j]，那么dp[i][j] 应该= dp[i-1][j-1] + 1。

如果text1[i] != text2[j]，该如何处理？
回到dp数组的含义，是text1[1…i] 和 text2[1…j]之间的最长公共子序列的长度，只是说最长长度，但没有说一定得包含text1[i]、text2[j]，并且题目也说了可以删除某些字符串中的某些字符，但不能改变顺序，所以当当前字符不等时，我们应该把当前字符删除掉，但删掉有两种删法：删掉text1[i]或者text2[j]，删哪一个？我们要保留最大值，所以dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

---

为什么不等的时候，不考虑dp[i-1][j-1]的情况？

因为dp[i-1][j]已经包含了dp[i-1][j-1]的情况，dp[i-1][j-1] 要么和dp[i-1][j]相等，要么dp[i-1][j-1] + 1 = dp[i-1][j]，所以情况是包含在内的。

---

综上，状态转移方程为：
if text1[i] == text2[j]：
dp[i][j] = dp[i-1][j-1]
if text1[i] != text2[j]：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

为了遍历所有的情况，所以得用两层循环，确保在i或者j确定的情况下，遍历完所有的j或i。

有了上述思考可以写出相应代码：（注意我们假设下标从1开始，因为这样方便讨论无字符的情况）

class Solution {public int longestCommonSubsequence(String text1, String text2) {int len1 = text1.length();int len2 = text2.length();int[][] dp = new int[len1 + 1][len2 + 1];for (int i = 0; i <= len1; i++) {dp[i][0] = 0;}for (int i = 0; i <= len2; i++) {dp[0][i] = 0;}// dp[i][j]：表示text1[1...i]与text2[1...j]的LCS长度// 注意不一定要包含text1[i]、text2[j]for (int i = 1; i <= len1; i++) {for (int j = 1; j <= len2; 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[len1][len2];}
}

※2.1.1最长重复子数组（中等）

注意题目要求，公共、不可删除。

dp[i][j]的含义，还是和之前一样吗？（上一道题的模板） 代表A[1…i]与B[1…j]的最长重复子数组的长度？

当A[i] == B[j]时，dp[i][j] = dp[i - 1][j - 1] + 1

当A[i] != B[j]时，dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

对不对呢？

举例
01111
10101

当 i 到 第3个数，j 到第5个数，A[i] == B[j]，dp[i][j] = dp[i - 1][j - 1] + 1 = 2 + 1 = 3，很显然是错的，应该是 2。因为上面的转移方程是对可以删除元素可言的，如果不可以删除元素，一旦元素不等，应该置0，即dp[i][j] = 0，一旦置零了，dp数组的含义也变了，应该是A[1…i]和B[1…j]，并且必须以A[i]和B[j]结尾的最长重复子数组的长度。

class Solution {public int findLength(int[] nums1, int[] nums2) {int len1 = nums1.length;int len2 = nums2.length;int[][] dp = new int [len1 + 1][len2 + 1];// dp[i][j]: nums1[1...i] 与 nums2[1...j]的最长公共重复子数组// 注意题目中不允许删除// nums1[i] == nums2[j]: dp[i][j] = dp[i - 1][j - 1] + 1// nums1[i] != nums2[j]: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])int max = 0;for (int i = 1; i <= len1; i++) {for (int j = 1; j <= len2; j++) {if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = 0;}max = Math.max(max, dp[i][j]);}}return max;}
}

2.1.2两个字符的删除操作（中等）（改编题1）

按照题目意思，必须要让两个word相同，不同的话要通过删除相同。

dp[i][j]代表text1[1…i]与text2[1…j]之间的最小步数，先看一个串全为0的情况：
dp[i][0] = i，dp[0][j] = j，因为一个串为0，另一个串必须全部删除才能相同

再来看普通情况，当text1[i] == text2[j]时：
那就是两个串都不用删除，dp[i][j] = dp[i-1][j-1]

当text1[i] != text2[j]时，如何考虑？
要么删除text1[i]，要么删除text2[j]，考虑到dp数组的含义，一定要确保后面考虑的问题是独立的并且可以由前面的子问题推出，所以，dp[i][j] = min(dp[i-1][j], dp[i][j-1])+1，不考虑dp[i-1][j-1]是因为这种状态已经包含在内了。

实在不知道对不对，可以举例子验证！

class Solution {public int minDistance(String word1, String word2) {int len1 = word1.length();int len2 = word2.length();int[][] dp = new int[len1 + 1][len2 + 1];// dp[i][j]指word1[1...i] 与 word2[1...j]的最小步数for (int i = 0; i <= len1; i++) {dp[i][0] = i;}for (int i = 0; i <= len2; i++) {dp[0][i] = i;}// 删除或不删除某些字符，使得 word1和 word2相同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];} else {// 不相等dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;}}}return dp[len1][len2];}
}

2.1.3两个字符串的最小ASCII删除和（中等）（改编题2）

如果前面两道题搞懂了，这道题直接就可以写出，只是dp数组的含义、base case改变了，状态转移方程微调了一下而已。

dp数组的初始化变成了ASCII的加和。

dp[i][j]指，以text1[1…i]与text2[1…j]的最小ASCII码删除和，同样讨论两种情况，text1[i] == text2[j]；text1[i] != text2[j]，可以动手推一推（也可以从最简单的情况一步步往后推，或者写出来后用简单的情况来验证一下）。

class Solution {public int minimumDeleteSum(String s1, String s2) {int len1 = s1.length();int len2 = s2.length();int[][] dp = new int[len1 + 1][len2 + 1];// 要使得两个字符串相等所删除的字符的ASCII值最小// dp[i][j]是s1[1...i]与s2[1...j]的最小和int sum = 0;for (int i = 1; i <= len1; i++) {sum += s1.charAt(i - 1);dp[i][0] = sum;}sum = 0;for (int i = 1; i <= len2; i++) {sum += s2.charAt(i - 1);dp[0][i] = sum;}for (int i = 1; i <= len1; i++) {for (int j = 1; j <= len2; j++) {// 字符相等，直接从前面继承if (s1.charAt(i - 1) == s2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];} else {// 字符不等，就要比较ASCII码大小，看删除哪一个dp[i][j] = Math.min(dp[i - 1][j] + s1.charAt(i - 1), dp[i][j - 1] + s2.charAt(j - 1));}}}return dp[len1][len2];}
}

2.1.4不相交的线（中等）

画图，从最简单的情况推起，dp[i][j]表示nums1[1…i]与nums2[1…j]能够画出的最多的线。
当nums1[i] == nums2[j]，那就是可以画线，它一旦画了，那么nums1[i]和nums2[j]都不能作为线的端点，因为题目有要求。所以dp[i][j] = dp[i - 1][j - 1] + 1，直接想不容易想出来，可以举几个例子就可以推出来了。

当nums1[i] != nums2[j]，就是不能画线，那么nums1[i]或者nums2[j]就可以作为线的端点，所以dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])。

其实细细品味，这道题就是最长公共子序列，换汤不换药，状态转移方程都不变的。

class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int len1 = nums1.length;int len2 = nums2.length;// dp[i][j]:nums1[1...i]与nums2[1...j]最多可绘制的最大连线数int[][] dp = new int [len1 + 1][len2 + 1];// nums1[i] == nums2[j] dp[i][j] = dp[i - 1][j - 1] + 1// nums1[i] != nums2[j] dp[i][j] = max(dp[i-1][j], dp[i][j-1])for (int i = 1; i <= len1; i++) {for (int j = 1;j <= len2; 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 - 1][j], dp[i][j - 1]);}}}return dp[len1][len2];}
}

2.1.5编辑距离（困难）

这道题如果有了上面几道题的铺垫，是很容易想到的，主要还是word1[i] != word2[j]的时候需要理解一下，因为总共就三种情况，那我们对这三种情况做讨论不就行了吗，可以画出具体的DP数组，如下图：

图源：labuladong公众号编辑距离专题

由上图可以得知，每一个方块，只可能由其左上角、上方和左方转移得来，可以尝试后推出状态转移方程。其实遇到陌生的动态规划题目，如果能够直接画出dp数组来，是很容易得到方程的。

class 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++) {// 另一个字符串为空，可以进行删除操作，有多少删多少// 也可以在空串上一直插dp[i][0] = i;}for (int j = 1; j <= len2; j++) {dp[0][j] = j;}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]; } else {// 不相等，分三种情况讨论，dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);}}}return dp[len1][len2];}
}

2.1.6判断子序列（简单）（双指针、DP）

这道题如果用双指针做就很简单，用DP的话得想到LCS。

双指针的解法：

class Solution {public boolean isSubsequence(String s, String t) {int i = 0;int j = 0;if (s.length() == 0) {return true;}while (j < t.length()) {if (s.charAt(i) == t.charAt(j)) {i++;}if (i == s.length()) {break;}j++;}return i == s.length();}
}

DP解法：
很简单，按照LCS的解法，统计dp[i][j]，要注意s串不能删，只能删t串！ 看最后dp[len1][len2]的长度与len1是否相等即可。

class Solution {public boolean isSubsequence(String s, String t) {int len1 = s.length();int len2 = t.length();int[][] dp = new int[len1 + 1][len2 + 1];for (int i = 1; i <= len1; i++) {for (int j = 1; j <= len2; j++) {if (s.charAt(i - 1) == t.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {// 题目中只能删t串，不能删s串！dp[i][j] = dp[i][j - 1];}}}return dp[len1][len2] == len1;}
}

※※2.1.7不同的子序列（困难）

这道题乍一看有最长公共子序列的影子，因为每一种情况都可以看成s串的某个子串是否 = t，然后再统计满足的子串个数。

dp[i][j]数组代表s[1…i] 和 t[1…j]的条件下，s 的子序列在 t 中出现的次数。dp[i][0] = 1，对 i 从0 - len1 都成立，因为空串是所有串的子串，在统计空串出现的次数时，都应该是出现一次。

当s[i] == t[j] 时，以s = “rara” t = “ra” 为例，当i = 3, j = 1时，s[i] == t[j]。此时分为2种情况，s串用最后一位的a 和 不用最后一位的a。

• 如果用s串最后一位的a，那么t串最后一位的a也被消耗掉，此时的子序列其实=dp[i-1][j-1]
• 如果不用s串最后一位的a，那就得看"rar"里面是否有"ra"子序列的了，就是dp[i-1][j]
• 所以，dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

当s[i] != t[j] 时，因为不能删除 t 串，只能删除 s 串，所以dp[i][j] = dp[i - 1][j]。

class Solution {public int numDistinct(String s, String t) {int len1 = s.length();int len2 = t.length();int[][] dp = new int[len1 + 1][len2 + 1];// 如果 t 是空串，那只有一种情况for (int i = 0; i <= len1; i++) {dp[i][0] = 1;}for (int i = 1; i <= len1; i++) {for (int j = 1; j <= len2; j++) {if (s.charAt(i - 1) == t.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];} else {// 按照题目意思只能删除 s 串中的字符，t不能删dp[i][j] = dp[i - 1][j];}}}return dp[len1][len2];}
}

这道题其实不容易想到字符相同时的转移方程，可以经过尝试得出。

---

2.2只涉及单字符串、数组的问题

2.2.1回文子串（中等）

注意：具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

$$dp[i][j]数组表示s[i...j]是否能构成回文串$$

• 由上述定义可知，dp[i][i] = true（1 <= i <= n，这里我们假设s从下标1开始），因为每个字符自己是可以构成回文的
• 考虑不同字符，如果s[i] == s[j]（我们保证 1 <= i <= j <= n），那么dp[i][j] = dp[i + 1][j - 1]，从下面的图可以看出，如果dp[i + 1][j - 1]是回文，当s[i] = s[j]，dp[i][j]也应该是回文。所以，其实本题中的状态是从中间往两侧扩展的。
  
• 如果s[i] != s[j]，那么不管前面是不是回文串，s[i…j]都不可能是回文串，所以dp[i][j] = false。
• 考虑状态转移方程的通用性，当只有两个字符时，s[i] = s[j]，dp[i][j] = dp[i + 1][j - 1]，会导致 j 跑到 i 的前面，是无效的，那这种状态该如何转换？ 和只有一个字符的情况一样，我们特判即可，因为两个字符时，如果相等，那肯定是回文。同理，三个字符时，如果两侧字符相等，也肯定是回文，但是三个字符的状态可以由一个字符的状态转换得来，所以无需特判。

现在我们判断完了所有可能的回文串，回到题目，我们需要统计回文串的个数，那其实在状态转移的时候就可以判断并求和了。

※：还需要注意遍历字符串的顺序，因为dp[i][j] = dp[i + 1][j - 1]，我们必须要知道i + 1才能推出i。所以应该从 n 开始遍历 i。

---

三、如何确定数组遍历顺序？

1、遍历的过程中，所需的状态必须是已经计算出来的
2、遍历的终点必须是存储结果的那个位置（本题的结果是dp[1][n]）

---

class Solution {public int countSubstrings(String s) {// dp[i][j] s[i...j]能否构成回文串int n = s.length();boolean[][] dp = new boolean[n + 1][n + 1];int cnt = 0;for (int i = n; i >= 1; i--) {// 注意遍历的顺序：1、遍历的过程中，所需的状态必须是已经计算出来的// 2、遍历的终点必须是存储结果的那个位置（本题的结果是dp[1][n]）// j 比 i小无意义，忽略掉for (int j = i; j <= n; j++ ) {if (s.charAt(i - 1) == s.charAt(j - 1)) {if (j - i == 1 || j == i) {// 特判长度为 2 的情况dp[i][j] = true;cnt++;} else {dp[i][j] = dp[i + 1][j - 1];if (dp[i][j]) {cnt++;}}} else {dp[i][j] = false;}}}return cnt;}
}

2.2.2最长回文子串（中等）

有了上一题的铺垫，本题也就很简单了，用dp数组记录s[i…j]能否构成回文串，再判断能构成回文串的情况下，最长的回文串。

class Solution {public String longestPalindrome(String s) {int n = s.length();if (n == 1) {return s;}boolean[][] dp = new boolean[n + 1][n + 1];// dp[i][j] = dp[i + 1][j - 1]int max = 1;// 认为下标从1开始int start = 1;for (int i = n; i >= 1; i--) {for (int j = i; j <= n; j++) {if (s.charAt(i - 1) == s.charAt(j - 1)) {if (j - i == 1 || j == i) {// 特判两个字符和一个字符的情况dp[i][j] = true;} else {dp[i][j] = dp[i + 1][j - 1];}}// 更新最长回文串if (dp[i][j] == true && max < (j - i + 1)) {start = i;max = j - i + 1;}}}// 注意substring的使用！return s.substring(start - 1, start - 1 + max);}
}

2.2.3最长回文子序列（中等）

整体思路和前几道题类似，只是题目多了一句可以删除或不删除字符，意思就是在s[i] != s[j]时，状态转移方程会有所不同。

如果s[i] != s[j]，那我们可以删除s[i]，也可以删除s[j]（同时删除的情况已经包含在内），最长回文串只可能在那两种情况下产生。所以，dp[i][j] = max (dp[i + 1][j], dp[i][j - 1]）

class Solution {public int longestPalindromeSubseq(String s) {int n = s.length();int[][] dp = new int[n + 1][n + 1];// s[i] == s[j] : dp[i][j] = dp[i+1][j-1] + 2// s[i] != s[j] : dp[i][j] = max(dp[i+1][j], dp[i][j-1])for (int i = n; i >= 1; i--) {for (int j = i; j <= n; j++) {if (i == j) {dp[i][j] = 1;} else {if (s.charAt(i - 1) == s.charAt(j - 1)) {if (j - i == 1) {// 先特判两个字符的情况，因为无法通过方程转移得到dp[i][j] = 2;} else {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[1][n];}
}

2.2.4最大子数组和（简单）

考虑一个元素有两种状态：选它不选它。

class Solution {public int maxSubArray(int[] nums) {int n = nums.length;int[] dp = new int[n + 1];// dp[i]，以第i个数结尾的最大子数组的和// 注意子数组至少包含一个元素dp[1] = nums[0];// 对于一个数，我们可以选或者不选int max = dp[1];for (int i = 2; i <= n; i++) {dp[i] = Math.max(dp[i - 1] + nums[i - 1], nums[i - 1]);max = Math.max(dp[i], max);}return max;}
}

2.2.5最长连续递增序列（简单）

注意题目，不允许删除，必须连续，严格递增，也是根据元素的两种状态写转移方程，dp[i]指，以第i个元素结尾的最长连续递增序列的长度。

class Solution {public int findLengthOfLCIS(int[] nums) {int n = nums.length;int[] dp = new int[n + 1];// 以第i个数结尾的最长连续递增序列（不能删除）dp[1] = 1;int max = 1;for (int i = 2; i <= n; i++) {if (nums[i - 1] > nums[i - 2]) {dp[i] = dp[i - 1] + 1;} else {dp[i] = 1;}max = Math.max(max, dp[i]);}return max;}
}

2.2.6最长递增子序列（中等）

注意题目的含义，严格递增，数组元素的位置不可调换，但可以删除！，考虑数组中某一个元素nums[i]，dp[i]表示以第 i 个元素结尾的最长严格递增子序列的长度，所以，dp[i] = max(dp[j]) + 1，j 是指在 i 下标之前的 且 严格小于nums[i]的数，需要遍历所有的情况，因为可能中间的元素有被删除，例如：2 1 3，这个结果应该是2，因为1可以删除。

经过上面分析，其实本题也是需要遍历所有的情况，只不过判断条件不同了。

class Solution {public int lengthOfLIS(int[] nums) {// 最长严格递增子序列，可以删除，但不能改变元素顺序// dp[i]，以第 i 个数结尾的最长递增子序列的长度int n = nums.length;int[] dp = new int[n];// 第 0 个数，就只有一个数，长度为1dp[0] = 1;// dp[i] = max(dp[j]) + 1，max(dp[i])是指前面能够构成严格递增子序列的最长长度int max_len = 1;// 遍历所有的可能情况for (int i = 1; i < n; i++) {// 默认就是只有自己，长度为1dp[i] = 1;for (int j = 0; j < i; j++) {if (nums[j] < nums[i]) {dp[i] = Math.max(dp[j] + 1, dp[i]);} }max_len = Math.max(max_len, dp[i]);}return max_len;}
}

---

单数组、字符串模板

除了回文子串题型，一般都是用一维DP数组解，dp[i]，表示以第i个元素结尾的xxx。

回文串，则是用二维DP数组，dp[i][j]，表示子串[i…j]是否为回文条件。

---

两个数组、字符串模板

一般都是用二维DP数组，dp[i][j]，表示t[1…i]和s[1…j]的xxxx条件。注意最长重复子数组的dp数组含义，加了一重以第 i 个数、第 j 个数结尾的条件。

同时不管是哪种情况，都一定要注意遍历的方向。

---