动态规划一直是面试中的经典难题，所见体型常规的有：0-1背包，完全背包，打家劫舍，股票问题，编辑距离，回文串。后续的一段时间会对动态规划专题做出总结。
647. 回文子串1.题目
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc" 输出：3 解释：三个回文子串: "a", "b", "c" 示例 2： 输入：s = "aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
1 <= s.length <= 1000s 由小写英文字母组成
2.思路
要首先明确，回文子串是连续的，回文子序列是不连续的
第一种思路，暴力解法两重for循环遍历输入字符串的起始位置和终止位置，然后判断这个区间是不是回文子串，时间复杂度O(n^3)显然不是最优解
动态规划
确定dp数组以及其下标的含义，布尔类型的dp[i] [j],表示字符串起始位置为i终止位置是j内的字符串是不是回文串，如果是true否则为false
确定递推公式，当s.charAt(i)和s.charAt(j)不相等的时候,dp[i][j]一定是false，当相等的时候分三种情况
- 情况一："a"i和j相等的时候此时直接为true情况二："aa"i和j相差为1的时候也为true情况三："acaca"此时，这种情况下是否满足回文串是由中间的字符串决定的，减去两头的"a"以后也就是查看dp[i+1] [j -1]位置是否为回文串
使用代码表示这四种情况的话
if (s.charAt(i) != s.charAt(j)) {
dp[i][j] = false;
} else {
if (j - i <= 1) {
dp[i][j] = true;
} else if (dp[i + 1][j - 1]) {
dp[i][j] = true;
}
}
初始化dp数组，不需要初始化直接操作即可
确定遍历顺序，从递推公式可以看出，当情况三出现的时候当前dp[i] [j]依赖于dp[i+1] [j-1]，所以遍历顺序应该是从下往上，从左往右，记住遍历的过程要时刻记住dp数组的含义
- 打印dp数组，以本题为例子”aaa“为例子
3.代码
class Solution {
public int countSubstrings(String s) {
//dp[i][j]表示以i和j为起始和终止为子串是否为回文子串
boolean[][] dp = new boolean[s.length()][s.length()];
int result = 0;
//遍历顺序很重要，因为根据状态转移方程可以知道，当前是否是回文串依赖于dp[i + 1][j - 1]即依赖下一行所以我们必须从下往上，从右往左
for (int i = s.length() - 1; i >= 0; i--) {
for (int j = i; j < s.length(); j++) {
//如果两个字符不等那么就肯定不是回文串
if (s.charAt(i) != s.charAt(j)) {
dp[i][j] = false;
//如果两个字符相当那么分以下三种情况
} else {
//1.i == j那么一定是回文串
//2.i - j小于1那么例如aa，或者aba一定也是回文串
if (j - i <= 1) {
result++;
dp[i][j] = true;
//3.i - j大于1那么例如cabac，如果c = c那么就是比较aba也就是i + 1, j - 1
} else if (dp[i + 1][j - 1]) {
result++;
dp[i][j] = true;
}
}
}
}
return result;
}
}
5. 最长回文子串
1.题目
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。 示例 2： 输入：s = "cbbd" 输出："bb" 示例 3： 输入：s = "a" 输出："a" 示例 4： 输入：s = "ac" 输出："a"
提示：
1 <= s.length <= 1000s 仅由数字和英文字母（大写和/或小写）组成
2.思路
确定dp数组以及其下标的含义，int类型的dp[i] [j],表示回文子串的长度，也就是说加入不是回文串长度为0
确定递推公式，当s.charAt(i)和s.charAt(j)不相等的时候,dp[i][j]一定是false，当相等的时候分三种情况
情况一："a"i和j相等的时，dp[i] [j] = 1
情况二："aa"i和j相差为1的时，dp[i] [j] = 2
情况三："acaca"此时，这种情况下是否满足回文串是由中间的字符串决定的，减去两头的"a"以后也就是查看dp[i+1] [j -1]位置是否为回文串，如果不为0的话那么长度就是dp[i + 1] [j - 1] + 2
使用代码表示这四种情况的话
if (s.charAt(i) == s.charAt(j)) {
if (i == j) { // 'a'
dp[i][j] = 1;
} else if (j - i == 1) { // 'aa'
dp[i][j] = 2;
} else if (dp[i + 1][j - 1] != 0){ // "abba"
dp[i][j] = dp[i + 1][j - 1] + 2;
}
if (end - start + 1 <= dp[i][j]) {
start = i;
end = j;
}
}
// 不相等就是0不需要显示表示
初始化dp数组，不需要初始化直接操作即可
确定遍历顺序，从递推公式可以看出，当情况三出现的时候当前dp[i] [j]依赖于dp[i+1] [j-1]，所以遍历顺序应该是从下往上，从左往右，记住遍历的过程要时刻记住dp数组的含义
- 打印dp数组，以本题为例子”babad“为例子
3.代码
class Solution {
public String longestPalindrome(String s) {
int[][] dp = new int[s.length()][s.length()];
int start = 0, end = 0;
for (int i = s.length() - 1; i >= 0; i--) {
for (int j = i; j < s.length(); j++) {
if (s.charAt(i) == s.charAt(j)) {
if (i == j) {
dp[i][j] = 1;
} else if (j - i == 1) {
dp[i][j] = 2;
} else if (dp[i + 1][j - 1] != 0){
dp[i][j] = dp[i + 1][j - 1] + 2;
}
if (end - start + 1 <= dp[i][j]) {
start = i;
end = j;
}
}
}
}
return s.substring(start, end + 1);
}
}
516. 最长回文子序列
1.题目
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" 。 示例 2： 输入：s = "cbbd" 输出：2 解释：一个可能的最长回文子序列为 "bb" 。
提示：
1 <= s.length <= 1000s 仅由小写英文字母组成
2.思路
这道题和先前不同的是，之前求的是回文子串是连续的而这道题是子序列是不连续的
确认dp数组以及下标含义，dp[i] [j]表示起始位置为i终止位置为j的字符串中最长回文子序列的长度
确认递归公式，记住在确认递归公式的时候要时刻记着dp数组的含义
- 当s.charAt(i) == s.charAt(j)的时候，只需要dp[i + 1] [j - 1]的长度即可即,dp[i + 1] [j - 1] + 2
当不相等的时候，说明当前两个字符,s.charAt(i)和s.charAt(j)不能同时加入，那么就分别加入s.charAt(i)和s.charAt(j)，试试哪个能够组成最长子序列
if (s.charAt(i) == s.charAt(j)) {
if (i == j) dp[i][j] = 1;
else dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
初始化dp数组，无需初始化代码安排好了
确定遍历顺序，从状态转移方程可以看出，当不相等的情况出现的时候，当前dp数组的值由下一行来决定，所以遍历顺序一定是从下往上，从左往右
打印dp数组
3.代码
class Solution {
public int longestPalindromeSubseq(String s) {
int[][] dp = new int[s.length()][s.length()];
for (int i = s.length() - 1; i >= 0; i--) {
for (int j = i; j < s.length(); j++) {
if (s.charAt(i) == s.charAt(j)) {
if (i == j) dp[i][j] = 1;
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[0][s.length() - 1];
}
}
总结
回文子串系列的题目就总结到这里，这类型动态规划的一个易错点在于遍历顺序。
