动态规划 - 3（ 回文串问题 两个数组的 dp 问题 7000 字详解）

一：回文串问题

1.1 回文子串

题目链接：回文子串

class Solution {public int countSubstrings(String s) {// 采用动态规划的思想解决问题，首先创建一个 dp 表，其中 dp[i][j] 表示 s[i...j] 是否是回文子字符串int n = s.length();boolean[][] dp = new boolean[n][n];int ret = 0;// 无需初始化直接开始从下网上填表，因为填表时只需要用到上三角的区间，所以 i 是减减的，j 是加加的for(int i = n - 1; i >= 0; i--){for(int j = i; j < n; j++){if(s.charAt(i) == s.charAt(j)){if(i == j || i + 1 == j) dp[i][j] = true;else if(i + 1 < j) dp[i][j] = dp[i + 1][j - 1];}// 更新一下 retif(dp[i][j] == true) ret += 1;}}return ret;}
}

1.2 最长回文子串

题目链接：最长回文子串

class Solution {public String longestPalindrome(String s) {// 采用动态规划的思想解决问题,首先创建一个 dp 表，其中 dp[i][j] 表示 s[i...j] 是否是回文子串int n = s.length();boolean[][] dp = new boolean[n][n];// 因为无需初始化所以直接从下往上直接填表int begin = 0, len = 1;for(int i = n - 1; i >= 0; i--){for(int j = i; j < n; j++){if(s.charAt(i) == s.charAt(j)){if(i == j || i + 1 == j) dp[i][j] = true;else if(i + 1 < j) dp[i][j] = dp[i + 1][j - 1];}// 接着看一下要不要更新 begin 和 lenif(dp[i][j] == true && j - i + 1 > len){len = j - i + 1;begin = i;}}}return s.substring(begin, begin + len);}
}

1.3 回文串分割 IV

题目链接：回文串分割 IV

class Solution {public boolean checkPartitioning(String s) {// 采用动态规划的方法解决问题，首先利用 dp 处理一下所有的子串是否回文int n = s.length();boolean[][] dp = new boolean[n][n];// 无需初始化直接开始填表for(int i = n - 1; i >= 0; i--){for(int j = i; j < n; j++){if(s.charAt(i) == s.charAt(j)){if(i == j || i + 1 == j) dp[i][j] = true;else if(i + 1 < j) dp[i][j] = dp[i + 1][j - 1];}}}// 循环结束后 dp 表就存储着所有子串是否是回文的信息了，接下来用两层 for 循环固定两个数暴力枚举一下就可以了// 第一段是 s[0...i-1]// 第二段是 s[i...j]// 第三段是 s[j+1...n-1]for(int i = 1; i < n - 1; i++)for(int j = i; j < n - 1 ;j++)if(dp[0][i - 1] == true && dp[i][j] == true && dp[j + 1][n - 1] == true) return true;return false;}
}

1.4 回文串分割 II

题目链接：回文串分割 II

class Solution {public int minCut(String s) {// 采用动态规划的思想解决问你题，首先将所有子串是否是回文串的信息填入 isPal 中int n = s.length();boolean[][] isPal = new boolean[n][n];// 因为无需初始化，所以直接从下往上填表for(int i = n - 1; i >= 0; i--){for(int j = i; j < n; j++){if(s.charAt(i) == s.charAt(j)){if(i == j || i + 1 == j) isPal[i][j] = true;else if(i + 1 < j) isPal[i][j] = isPal[i + 1][j - 1];}}}// 循环结束后 isPal 就存储了所有子串的回文串信息了，接下来开始创建 dp 表， dp[i] 表示字符串 s[0...i] 的最小回文切割次数int[] dp = new int[n];// 接着开始把所有元素的值初始化为正无穷大for(int i = 0; i < n; i++) dp[i] = Integer.MAX_VALUE;// 接着开始正式的操作了,遍历字符串的每个位置，计算最小切割次数for(int i = 0; i < n; i++){if(isPal[0][i] == true) dp[i] = 0;else if(isPal[0][i] == false){// 否则，我们需要从 j = 1 到 i 遍历，找到一个使得 dp[i] 最小的 jfor (int j = 1; j <= i; j++) {if (isPal[j][i]) dp[i] = Math.min(dp[i], dp[j - 1] + 1);}} }return dp[n - 1];}
}

1.5 最长回文子序列

题目链接：最长回文子序列

class Solution {public int longestPalindromeSubseq(String s) {// 采用动态规划的思想解决问题，创建一个 dp 表，其中 dp[i][j] 表示字符串 s[i...j] 的最长回文子序列的长度int n = s.length();int[][] dp = new int[n][n];// 因为无需初始化，所以直接开始从下往上，从左往右进行填表for(int i = n - 1; i >= 0; i--){// 因为填表需要用到上右三角，对于对角线的元素需要特殊处理，因为他们此时代表一个字符dp[i][i] = 1;for(int j = i + 1; j < n; 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][j - 1], dp[i + 1][j]);}}return dp[0][n - 1];}
}

1.6 让字符串成为回文串的最小插入次数

题目链接：让字符串成为回文串的最小插入次数

class Solution {public int minInsertions(String s) {// 首先创建一个 dp 数组，dp[i][j] 表示子串 s[i...j] 转换为回文所需的最少插入次数int n = s.length();int[][] dp = new int[n][n];// 接着从下往上，从左往右开始填表for (int i = n - 1; i >= 0; i--) {for (int j = i + 1; j < n; j++) {if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i + 1][j - 1]; else dp[i][j] = Math.min(dp[i][j - 1], dp[i + 1][j]) + 1;}}return dp[0][n - 1]; }
}

二：两个数组的 dp 问题

2.1 最长公共子序列

题目链接：最长公共子序列

class Solution {public int longestCommonSubsequence(String text1, String text2) {// 采用动态规划的思想解决这个问题，首先创建一个 dp 表，dp[i][j] 表示 s1[0...i-1] 和 s2[0...j-1] 的最长公共子序列的长度。int m = text1.length(), n = text2.length();int[][] dp = new int[m + 1][n + 1];// 为了简化边界条件，我们在每个字符串的开头添加一个空格字符，使得 s1 和 s2 的下标从 1 开始，而不是从 0 开始。text1 = " " + text1; text2 = " " + text2; // 因为多加的一行和一列要初始化为 0，而数组的默认值就为 0 ，所以初始化部分不用做处理，接着就开始从上往下，从左往右填表for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){if(text1.charAt(i) == text2.charAt(j)) 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];}
}

2.2 不相交的线

题目链接：不相交的线

class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {// 采用动态规划的思想解决问题，首先创建一个 dp 表，dp[i][j] 表示 nums1[0...i-1] 和 nums2[0...j-1] 的最大不交叉线数int m = nums1.length,n = nums2.length;int[][] dp = new int[m + 1][n + 1];// 因为多加的一行和一列都初始化为 0 ，此处直接跳过开始从上往下，从左往右填表for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){// 此处要注意，我们现在是在遍历 dp 表，此时如果要找到对应的原始数组中的数据要让 i 和 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];}
}

2.3 不同的子序列

题目链接：不同的子序列

class Solution {public int numDistinct(String s, String t) {// 首先创建一个 dp 表，dp[i][j] 表示 s[0...j-1] 中有多少个子序列等于 t[0...i-1]int m = t.length(), n = s.length();int[][] dp = new int[m + 1][n + 1];// 接着开始初始化 dp 数组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][j - 1];if (t.charAt(i - 1) == s.charAt(j - 1)) dp[i][j] += dp[i - 1][j - 1]; }}return dp[m][n];}
}

2.4 通配符匹配

题目链接：通配符匹配

class Solution {public boolean isMatch(String ss, String pp) {// 首先创建一个 dp 表，dp[i][j] 表示 ss 的前 i 个字符是否与 pp 的前 j 个字符匹配int m = ss.length(), n = pp.length(); boolean[][] dp = new boolean[m + 1][n + 1]; // 接着把 ss 和 pp 转为字符数组方便操作，为了简化边界条件，我们在每个字符串的开头添加一个空格字符，使得 s1 和 s2 的下标从 1 开始，而不是从 0 开始。ss = " " + ss;  pp = " " + pp; char[] s = ss.toCharArray(); char[] p = pp.toCharArray(); // 接着开始初始化，第一行的初始化要判断一下dp[0][0] = true; for (int j = 1; j <= n; j++) {if (p[j] == '*') dp[0][j] = true;else break; }// 接着开始从上往下，从左往右填表for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) { if (p[j] == '*') dp[i][j] = dp[i - 1][j] || dp[i][j - 1];else dp[i][j] = (p[j] == '?' || p[j] == s[i]) && dp[i - 1][j - 1];}}return dp[m][n];}
}

2.5 正则表达式匹配

题目链接：正则表达式匹配

class Solution {public boolean isMatch(String ss, String pp) {// 首先创建一个 dp 表，dp[i][j] 表示 ss 的前 i 个字符是否与 pp 的前 j 个字符匹配int m = ss.length(), n = pp.length(); boolean[][] dp = new boolean[m + 1][n + 1];// 接着把 ss 和 pp 转为字符数组方便操作，为了简化边界条件，我们在每个字符串的开头添加一个空格字符，使得 s1 和 s2 的下标从 1 开始，而不是从 0 开始。ss = " " + ss;  pp = " " + pp; char[] s = ss.toCharArray(); char[] p = pp.toCharArray(); // 接着开始初始化 dp 表，dp 表的第一行是需要特判的dp[0][0] = true; for (int j = 2; j <= n; j += 2) {if (p[j] == '*') dp[0][j] = true;else break; }// 开始从上到下，从左往右填表for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p[j] == '*') dp[i][j] = dp[i][j - 2] || (p[j - 1] == '.' || p[j - 1] == s[i]) && dp[i - 1][j];else dp[i][j] = (p[j] == '.' || p[j] == s[i]) && dp[i - 1][j - 1];}}return dp[m][n];}
}

2.6 交错字符串

题目链接：交错字符串

class Solution {public boolean isInterleave(String s1, String s2, String s3) {// 采用动态规划的思想解决问题，首先创建一个 dp 表， dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符是否能交织成 s3 的前 i + j 个字符int m = s1.length(), n = s2.length();boolean[][] dp = new boolean[m + 1][n + 1];// 特殊情况if (m + n != s3.length()) return false;// 为了简化边界条件，我们在每个字符串的开头添加一个空格字符，使得 s1 和 s2 的下标从 1 开始，而不是从 0 开始。s1 = " " + s1; s2 = " " + s2; s3 = " " + s3;// 接着开始初始化 dp 表。先初始化第一行dp[0][0] = true;for(int j = 1; j <= n; j++){if(s2.charAt(j) == s3.charAt(j)) dp[0][j] = true;else break; // 出现第一个不匹配的后面全都是 false，此处不用处理，因为默认值就是 false}// 接着初始化第一列for(int i = 1; i <= m; i++){if(s1.charAt(i) == s3.charAt(i)) dp[i][0] = true;else break;}// 接着从上往下，从左往右填表for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){dp[i][j] = (s1.charAt(i) == s3.charAt(i + j) && dp[i - 1][j] == true) || (s2.charAt(j) == s3.charAt(i + j) && dp[i][j - 1] == true);}}return dp[m][n];}
}

2.7 两个字符串的最小 ASCII 删除和

题目链接：两个字符串的最小 ASCII 删除和

class Solution {public int minimumDeleteSum(String s1, String s2) {// 首先创建一个 dp 表，dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符的最长公共子序列的字符和int m = s1.length(), n = s2.length();int[][] dp = new int[m + 1][n + 1]; // 接着初始化 dp 表，因为要初始化的行和列都为 0 ，所以这里就不做处理// 接着从上往下，从左往右填 dp 表for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (s1.charAt(i - 1) == s2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i - 1);else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}// 最后计算 s1 和 s2 中所有字符的 ASCII 和int sum = 0;// 先计算 s1 中所有字符的 ASCII 值之和for (char ch : s1.toCharArray()) sum += ch;// 再计算 s2 中所有字符的 ASCII 值之和for (char ch : s2.toCharArray()) sum += ch;return sum - 2 * dp[m][n];}
}

2.8 最长重复子数组

题目链接：最长重复子数组

class Solution {public int findLength(int[] nums1, int[] nums2) {// 采用动态规划的思想解决问题。首先创建一个 dp 表，dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组的长度int m = nums1.length, n = nums2.length;int[][] dp = new int[m + 1][n + 1];// 因为要初始化的行和列都是 0 ，此处采用默认值即可，所以我们直接开始从上往下填表,一边填表一边记录表中的最大值int ret = 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;ret = Math.max(ret, dp[i][j]);}}return ret;}
}