【动态规划】回文串问题
1. 回文子串
647. 回文子串
在求回文串的时候，暴力解法就是，先确定开头，然后依次遍历每一个结尾位置是否为回文串，然后再换下一个开头，也就是一个二维数组的遍历方式，当换一个开头的时候，前面的就不用再遍历了
状态表示：dp[i][j] 表示以 i 开头，以 j 结尾的字符串是否为回文串
状态转移方程：
当 i , j 的字符不相等时，以 i 开头，以 j 结尾的字符串肯定就不是回文串，当 i , j 位置字符相等时就又分为三种情况，一种是只有两个字符，一种是有三个字符，另一种就是其它，前两种肯定也是回文串，第三种再求是否是回文串也就是 dp[i + 1][j - 1]
初始化：当 i 和 j 重叠时或者 i + 1 = j 时 dp[i + 1][j - 1] 才会越界，但是这两种情况已经处理过了，所以也不会越界，不需要做特殊初始化
填表顺序：当填 dp[i][j] 时需要用到左下角的数据，所以说就要从下往上填
返回值：遍历 dp 表，所有为 true 的个数就是回文串的个数
内层循环从 i 开始就可以了，不用再去从 0 开始，从 0 开始后面还是会越界
class Solution {public int countSubstrings(String s) {int n = s.length();char[] c = s.toCharArray();boolean[][] dp = new boolean[n][n];int res = 0;for(int i = n - 1;i >= 0;i--){for(int j = i;j < n;j++){if(c[i] != c[j]){dp[i][j] = false;}else{if(i == j || i + 1 == j) dp[i][j] = true;else dp[i][j] = dp[i + 1][j - 1];}if(dp[i][j]) res++;}}return res;}
}2. 最长回文子串
5. 最长回文子串
这题和上题一样的思路，只需要额外定义变量去表示回文子串的长度，然后再记录一下起止下标，最后返回最长的回文子串即可
public String longestPalindrome(String s) {int n = s.length();boolean[][] dp = new boolean[n][n];char[] c = s.toCharArray();int ret = 0;int left = 0,right = 0;for(int i = n - 1;i >= 0;i--){for(int j = i;j < n;j++){if(c[i] == c[j]){dp[i][j] = (i + 1 < j) ? dp[i + 1][j - 1] : true;}if(dp[i][j] && j - i + 1 > ret){ret = j - i + 1;left = i;right = j;}}}return s.substring(left,right + 1);}dp 表中还可以直接存储回文子串的长度，如果不是回文子串就存储 0
public static String longestPalindrome(String s) {
int n = s.length();
int[][] dp = new int[n][n];
char[] c = s.toCharArray();
int ret = 0;
String ans = "";
for(int i = n - 1;i >= 0;i--){for(int j = i;j < n;j++){if(c[i] != c[j]) dp[i][j] = 0;else{if(i == j) dp[i][j] = 1;if(i + 1 == j) dp[i][j] = 2;if(i != j && i + 1 != j){if(dp[i + 1][j - 1] != 0){dp[i][j] = dp[i + 1][j - 1] + 2;}}if(ret < dp[i][j]){ret = dp[i][j];ans = s.substring(i,j + 1);}}}
}
return ans;
}3. 分割回文串 IV
1745. 分割回文串 IV
把一个字符串分为三个区间，只需要找出所有的三元组进行判断是否是回文串即可，可以像上面的那些题一样，把所有的回文串情况都用 dp 表来表示，这样在判断的时候就是 O(1) 的复杂度
分为三个区间，分别为：0 ~ i , i + 1 ~j , j + 1 ~ n - 1，所以在枚举的时候 i 是不能为 n - 2 的，不然剩下的就不能分为两个区间，同理，j 也不能为 n - 1
class Solution {public boolean checkPartitioning(String s) {int n = s.length();boolean[][] dp = new boolean[n][n];char[] c = s.toCharArray();for(int i = n - 1;i >= 0;i--){for(int j = i;j < n;j++){if(c[i] == c[j]){if(i == j || i + 1 == j){dp[i][j] = true;}else {dp[i][j] = dp[i + 1][j - 1];}}}}for(int i = 0;i < n - 1;i++){for(int j = i + 1;j < n - 1 ;j++){if(dp[0][i] && dp[i + 1][j] && dp[j + 1][n - 1]){return true;}}}return false;}
}4. 分割回文串 II
132. 分割回文串 II
状态表示：可以把 dp[i] 表示为 0 ~ i 区间中的最长子串的最小分割次数
状态转移方程：
如果说 0 ~ i 是回文串的话就不需要分割，也就是 0 ，如果不是回文串的话就需要来找出最小分割次数，可以先来从 j 位置分割一次，然后再判断 j ~ i 位置是否是回文，如果是的话就只需要求出 0 ~ j - 1 区间内的最小分割次数，如果不是的话，那么本次分割就不能构成回文串，也就不用更新结果
由于此时枚举的是每一个 j 的分割位置，更新 g[i] 时需要在本次所有的分割位置中找出一个最小值
判断是否是回文串还是可以像之前一样把所有可能都处理出来
初始化：为了不影响 g[i] = Math.min(g[j - 1] + 1,g[i]); 这里取的是最小值，所以 g[i] 不能初始化为 0，应该初始化为一个很大的数，所以数组 g 中的每一个元素都应该初始化为无穷大
填表顺序：从左往右
返回值：返回 g[n - 1] 即可
class Solution {public int minCut(String s) {int n = s.length();char[] c = s.toCharArray();boolean[][] f = new boolean[n][n];for(int i = n - 1;i >= 0;i--){for(int j = i;j < n;j++){if(c[i] == c[j]){if(i == j || i + 1 == j){f[i][j] = true;}else{f[i][j] = f[i + 1][j - 1];}}}}int[] g = new int[n];Arrays.fill(g,0x3f3f3f);for(int i = 0;i < n;i++){if(f[0][i]){g[i] = 0;}else{for(int j = 0;j <= i;j++){if(f[j][i]){g[i] = Math.min(g[j - 1] + 1,g[i]);}}}}return g[n - 1];}
}5. 最长回文子序列
516. 最长回文子序列
状态表示：
如果使用一个状态表示的话，是表示不出来之前的回文子序列状态的，所以可以使用二维 dp 来尝试一下
dp[i][j] 表示区间 [ i , j ] 内的所有子序列中最长回文子序列的长度
状态转移方程：
首先和判断回文串一样，判断 i , j 位置的字符是否相同，如果相同的话，就分为三种情况：i = j 时，也就意味着区间内只有一个字符，那么 dp 值就是 1，如果 i + j = j 的话，那么就意味着区间内是只有 i , j 两个元素， dp 值就是 2，其他情况就是找出从 i + 1，j - 1 区间内的最大值再加上 2
如果不相等的话，由于回文串子序列是可以不连续的，所以可以从 i + 1 , j 区间和 i , j - 1区间内找出一个最大值
初始化：和上面一样，特殊情况已经判断了，不需要初始化
填表顺序：
由于会用到下边和左边的值，所以填表顺序就是边从下往上，边从左到右，对角线上的元素，也就是 i = j 的情况都是 1 ，这一步可以直接把 dp[i][i] 初始化一下，后续 j 直接从 i + 1 枚举
返回值：dp[0][n - 1]
class Solution {public int longestPalindromeSubseq(String s) {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];}
}6. 让字符串成为回文串的最少插入次数
1312. 让字符串成为回文串的最少插入次数
状态表示：
dp[i][j]：以 i , j 位置结尾时，使它成为回文串的最小插入次数
状态转移方程：
当 i 和 j 位置字符相同时，那么就不需要插入字符，也就是可以从 i + 1, j - 1 区间继续找答案，不相同时，就分为插入一个元素和 i 或 j 相同，然后再从 i + 1 , j 或 i , j - 1 区间内找出最小值，再加上插入的这一步
初始化：由于可能越界的情况已经特判过了，所以不需要初始化
填表顺序：和之前一样，需要用到左下角元素，所以需要从下到上，从左到右填表
返回值：dp[0][n - 1]
class Solution {public int minInsertions(String s) {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 + 1][j],dp[i][j - 1]) + 1;}}}return dp[0][n - 1];}
}