解答这类题目, 省略不掉遍历, 因此我们先从遍历方式说起，通常我们遍历子串或者子序列有三种遍历方式
- 以某个节点为开头的所有子序列: 如 [a]，[a, b]，[ a, b, c] ... 再从以 b 为开头的子序列开始遍历 [b] [b, c]。即暴力解法。
- 根据子序列的长度为标杆，如先遍历出子序列长度为 1 的子序列，在遍历出长度为 2 的 等等。 leetcode (5. 最长回文子串 ) 中的解法就用到了。
- 以子序列的结束节点为基准，先遍历出以某个节点为结束的所有子序列，因为每个节点都可能会是子序列的结束节点，因此要遍历下整个序列，如: 以 b 为结束点的所有子序列: [a , b] [b] 以 c 为结束点的所有子序列: [a, b, c] [b, c] [ c ]。这里因为可以产生递推关系, 采用动态规划时, 经常通过此种遍历方式, 如 背包问题, 最大公共子串
====================== 子序问题（连续）======================
1.最大子序和（53 - 易）
题目描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。与剑指42相同。
示例 :
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
思路：典型的动态规划，关键点：
- dp[i]：以nums[i]为结尾的最大和的连续子数组（重要）
- 状态转移方程：dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])，因为元素可能存在负数。
由于dp[i]只依赖dp[i - 1]，所以可以用一个变量pre记录状态更替。
代码实现：
class Solution { // 动态规划(注意：最后返回的是所有位置中最大的) public int maxSubArray(int[] nums) { int n = nums.length; if (nums == null || n == 0) { return 0; } // dp[i]:以i结尾的最大子序和 int[] dp = new int[n]; dp[0] = nums[0]; int ans = nums[0]; for (int i = 1; i < n; i++) { dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]); ans = Math.max(ans, dp[i]); } return ans; } // 状态压缩 public int maxSubArray(int[] nums) { int n = nums.length; if (nums == null || n == 0) { return 0; } int pre = nums[0]; int ans = nums[0]; for (int i = 1; i < n; i++) { pre = Math.max(pre + nums[i], nums[i]); ans = Math.max(ans, pre); } return ans; } }
2.最长连续递增序列（674 - 易）
题目描述：给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
示例 :
输入：nums = [1,3,5,4,7] 输出：3 解释：最长连续递增序列是 [1,3,5], 长度为3。 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
思路：典型的动态规划：
- dp[i]：以nums[i]为结尾的最长连续递增序列的长度
- 状态转移方程：如果递增：dp[i] = dp[i - 1] + 1，否则dp[i] = 1。
由于dp[i]只依赖dp[i - 1]，所以可以用一个变量pre记录状态更替。
代码实现：
class Solution { // 动态规划（最后返回整个数组中最长的连续递增子序列） public int findLengthOfLCIS(int[] nums) { int n = nums.length; if (nums == null || n == 0) { return 0; } int[] dp = new int[n]; dp[0] = 1; int ans = 1; for (int i = 1; i < n; i++) { if (nums[i] > nums[i - 1]) { dp[i] = dp[i - 1] + 1; } else { dp[i] = 1; } ans = Math.max(ans, dp[i]); } return ans; } // 状态压缩 public int findLengthOfLCIS(int[] nums) { int n = nums.length; if (nums == null || n == 0) { return 0; } int pre = 1; int ans = 1; for (int i = 1; i < n; i++) { if (nums[i] > nums[i - 1]) { pre = pre + 1; } else { pre = 1; } ans = Math.max(ans, pre); } return ans; } }
3.最长重复子数组（718 - 中）
题目描述：给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例 :
输入： A: [1,2,3,2,1] B: [3,2,1,4,7] 输出：3 解释： 长度最长的公共子数组是 [3, 2, 1] 。
思路：典型的动态规划：
dp[i][j]：以nums1[i]和nums2[j]为结尾的最长公共子数组。- 状态转移方程：相等：
dp[i][j] = dp[i - 1][j - 1] + 1，否则dp[i][j] = 0。（即以nums1[i] 和 nums2[j] 结尾的公共子数组为0！因为要求连续！）
ps：为了简化代码，我们判断条件是nums[i - 1]和nums[j - 1]！
空间压缩：逆序遍历，保证不覆盖。
代码实现：
class Solution { // 动态规划 public int findLength(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; if (m == 0 || n == 0) { return 0; } int[][] dp = new int[m + 1][n + 1]; int ans = 0; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (nums1[i - 1] == nums2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = 0; } ans = Math.max(ans, dp[i][j]); } } return ans; } // 空间压缩：dp[i][j]只依赖dp[i - 1][j - 1]，这里压缩到一列！ public int findLength(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; if (m == 0 || n == 0) { return 0; } int[] dp = new int[n + 1]; int ans = 0; for (int i = 1; i <= m; i++) { for (int j = n; j >= 1; j--) { if (nums1[i - 1] == nums2[j - 1]) { dp[j] = dp[j - 1] + 1; } else { dp[j] = 0; } ans = Math.max(ans, dp[j]); } } return ans; } }
====================== 子序问题（不连续）=====================
1.最长公共子序列（1143 - 中）
题目描述：给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 :
输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。
思路：典型动态规划，类比T718，但这里是是不连续的：
- 当前两个字符，我们可以利用之前的结果
- 故，最终结果不需要遍历整个数组，最后一个就是全局最大。
代码实现：
class Solution { // 动态规划 public int longestCommonSubsequence(String text1, String text2) { int m = text1.length(), n = text2.length(); int[][] dp = new int[m + 1][n + 1]; 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][j - 1], dp[i - 1][j]); } } } return dp[m][n]; } }
2.最长递增子序列（300 - 中）
题目描述：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 :
输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
思路：基本解法是动态规划，对比T674（连续），不同点：
- 由于不连续，当前位置依赖依赖1~i-1位置的值（不能压缩空间）
- 当出现不递增时，我们不做操作，只有递增才遍历更新最大值。
- dp数组所有元素初始化为1（初始最长递增子序列是其本身）。
另外本题最优解：贪心+二分。思路比较巧妙，新建数组 cell，用于保存最长上升子序列。对原序列进行遍历，将每位元素二分插入 cell 中，（注意cell数组严格上升，故可以使用二分查找）。
- 如果插入元素大于cell数组中的最大值，直接加在后边；
- 否则，用它覆盖掉cell数组中比它大的元素中最小的那个（因为已经有序所以可以使用二分查找）。比如：cell中已经有[1, 3, 5]，插入2，则覆盖3，cell数组变为[1, 2, 5]
总之，思想就是让 cell 中存储比较小的元素。重要，cell 未必是真实的最长上升子序列，但长度是对的!
代码实现：
class Solution { // 动态规划 public int lengthOfLIS(int[] nums) { int n = nums.length; if (n <= 1) return n; // dp[i]：以i结尾的最长严格递增子序列的长度 int[] dp = new int[n]; Arrays.fill(dp, 1); int ans = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { // 注意：不能进行空间压缩，因为当前位置i依赖1~i-1位置的值 if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } ans = Math.max(ans, dp[i]); } return ans; } public int lengthOfLIS(int[] nums) { int n = nums.length; if (n <= 1) return n; // cell存储比较小的元素 int[] cell = new int[n]; cell[0] = nums[0]; // index记录最长连续递增子序列的结束索引 int index = 0; for (int i = 1; i < n; i++) { int l = 0, r = index; if (nums[i] > cell[index]) { index++; cell[index] = nums[i]; } else { while (l < r) { int mid = l + ((r - l) >> 1); if (nums[i] > cell[mid]) { l = mid + 1; } else { r = mid; } } cell[l] = nums[i]; } } return index + 1; } }
3.不相交的线（1035 - 中）
题目描述：在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：
nums1[i] == nums2[j]
且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
以这种方法绘制线条，并返回可以绘制的最大连线数。
示例 :
输入：nums1 = [1,4,2], nums2 = [1,2,4] 输出：2 解释：可以画出两条不交叉的线，如上图所示。 但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
思路：本题本质就是求最长公共子序列，与1143相同。代码相同，空间压缩省略。
代码实现：
class Solution { // 动态规划 public int maxUncrossedLines(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; if (m == 0 || n == 0) { return 0; } int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; 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[m][n]; } }
===================== 子序问题（编辑距离）=====================
1.不同的子序列（115 - 难）
题目描述：给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
题目数据保证答案符合 32 位带符号整数范围。
示例 :
输入：s = "rabbbit", t = "rabbit" 输出：3 解释： 如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。 (上箭头符号 ^ 表示选取的字母) rabbbit ^^^^ ^^ rabbbit ^^ ^^^^ rabbbit ^^^ ^^^
思路：本题是一个字符串匹配问题，即在主串s中找模式串t，要求：寻找s子序列中为t的个数（t是s的子序列）。典型动态规划，关键点：
dp[i][j]代表T前i字符串可以由S前j字符串组成最多个数。- 状态转移方程：注：当
s[j] == t[i]是，这里的j位置可选也可以不选。即主串中的j的位置。
- 当
S[j] == T[i] , dp[i][j] = dp[i-1][j-1] + dp[i][j-1];即只有相等，模式串才移动。 - 当
S[j] != T[i] , dp[i][j] = dp[i][j-1]
注意：dp数组开辟长度，因为s和t的子序列还有空字符串存在。
代码实现：
public int numDistinct(String s, String t) { int sl = s.length(), tl = t.length(); int[][] dp = new int[tl + 1][sl + 1]; // t字符串为空，空串是所有字符串的子集 for (int j = 0; j <= sl; j++) dp[0][j] = 1; for (int i = 1; i <= tl; i++) { for (int j = 1; j <= sl; j++) { if (t.charAt(i - 1) == s.charAt(j - 1)) // j位置选或者不选（输出所有的可能所以是+） dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1]; else dp[i][j] = dp[i][j - 1]; } } return dp[tl][sl]; }
2.判断子序列（392 - 易）
题目描述：给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
示例 :
输入：s = "abc", t = "ahbgdc" 输出：true
思路：本题动态规划比上题简单。
- 本题可以直接根据字符串的String.indexOf（char ch, int index）：查找字符在字符串中从指定位置开始第一次出现的索引，没有则返回-1。
- 也可以使用双指针进行比较，实现比较简单（推荐！）。
- 动态规划（效率较低）：字符串匹配问题，关键点：
dp[i][j]：s的前i个字符与t的前j个字符中公共子序列的长度（匹配的长度）- 状态转移方程：如果字符相同
dp[i][j] = dp[i - 1][j - 1] + 1，否则dp[i][j] = dp[i][j - 1]。ps：这里是判断s是否为t的子序列，当最后公共子序列长度 = m（s的长度），说明是子序列。
代码实现：
class Solution { // 库函数：判断索引是否存在 public boolean isSubsequence(String s, String t) { int index = -1; for (char ch : s.toCharArray()) { index = t.indexOf(ch, index + 1); if (index == -1) { return false; } } return true; } // 双指针 public boolean isSubsequence(String s, String t) { int m = s.length(), n = t.length(); int i = 0, j = 0; while (i < m && j < n) { if (s.charAt(i) == t.charAt(j)) { i++; } j++; } return i == m; } // 动态规划 public boolean isSubsequence(String s, String t) { int m = s.length(), n = t.length(); // dp[i][j]：s的前i个字符是否与t的前j个字符公共子序列的长度（匹配的长度） int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; 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]; } } } return dp[m][n] == m ? true : false; } }
待补充。。583， 72
===================== 子序问题（回文）=====================
1.最长回文子序列（516 - 中）
题目描述：给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
示例 :
输入:"bbbab" 输出:4 一个可能的最长回文子序列为 "bbbb"。
思路：本题目标是返回最长的回文子序列的长度，使用动态规划：
- dp数组：在子串
s[i..j]中，最长回文子序列的长度为dp[i][j]，最终目标是dp[0][n - 1]。 - 状态转移方程比较简单，相同添加（长度+2），不同选两个边界加与不加的最大值。
if (s[i] == s[j]) // 它俩一定在最长回文子序列中 dp[i][j] = dp[i + 1][j - 1] + 2; else // s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长？ dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
需要注意的是：根据一般位置的依赖关系（每个元素可能依赖左/下/左下元素），我们需要从左下角向右上角填元素。只需要从对角线开始（右上部分，即i <= j）。
代码实现：
class Solution { public int longestPalindromeSubseq(String s) { int n = s.length(); char[] cs = s.toCharArray(); int[][] dp = new int[n][n]; for (int i = 0; i < n; ++i) { dp[i][i] = 1; } for (int i = n - 1; i >= 0; i--) { for (int j = i + 1; j < n; j++) { if (cs[i] == cs[j]) { // 相等直接加入 dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]); } } } return dp[0][n - 1]; } }
2.最长回文子串（5 - 中）
题目描述：给你一个字符串 s，找到 s 中最长的回文子串。
示例 :
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
思路：本题比较容易想到的是中心扩散法：从每个位置向两边扩散，遇到不是回文的停止扩散。记录最长的回文子串.
- 要分奇数中心扩散和偶数中心扩散两种情况（取最大值）。
- 当上述最大值大于当前最长回文子串，更新最长会子串开始和结束位置。
- 遍历每个位置，然后扩散，时间复杂度O(N^2)。
显然上述会有大量的重复计算，可以使用动态规划进行优化：
dp[i][j]表示：子串 s[i..j] 是否为回文子串，这里子串 s[i..j] 定义为左闭右闭区间，即可以取到 s[i] 和 s[j]。- 根据头尾字符是否相等，需要分类讨论：
dp[i][j] = (s[i] == s[j]) and (dp[i + 1][j - 1] or j - i < 3)，包含奇偶情况。
代码实现：
class Solution { // 中心扩展法 public String longestPalindrome(String s) { char[] cs = s.toCharArray(); int len = cs.length; if (len < 2) { return s; } int start = 0; int end = 0; for (int i = 0; i < len; i++) { int len1 = extendSubString(cs, i, i); int len2 = extendSubString(cs, i, i + 1); int max = Math.max(len1, len2); if (max > end - start) { // 对于（如a b b a），i代表左b位置 start = i - (max - 1) / 2; end = i + max / 2; } } return s.substring(start, end + 1); } private int extendSubString(char[] cs, int left, int right) { while (left >= 0 && right < cs.length && cs[left] == cs[right]) { left--; right++; } // right - left + 1 - 2 return right - left - 1; } // 动态规划 public String longestPalindrome(String s) { char[] cs = s.toCharArray(); int len = s.length(); boolean[][] dp = new boolean[len][len]; int start = 0; int end = 0; int maxLen = 0; for (int j = 0; j < len; j++) { for (int i = 0; i < j; i++) { if (cs[i] == cs[j] && (dp[i + 1][j - 1] || j - i < 3)) { dp[i][j] = true; if (j - i + 1 > maxLen) { maxLen = j - i + 1; start = i; end = j; } } } } return s.substring(start, end + 1); } }
