day51【代码随想录】动态规划之回文子串、最长回文子序列

---

前言

1、回文子串
2、最长回文子序列

---

一、回文子串（力扣647）

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

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

分析：
1、确定dp[]数组以及下标含义

布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

2、递推公式
分析两种情况：
s[i]与s[j]相等，s[i]与s[j]不相等两种
当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。
当s[i]与s[j]相等时：

情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
情况二：i和j仅相差1，“aa” 这样子
情况三：i-j>1 “abccba” 或者 “abca”，此时我们需要判断i-1 和 j+1是不是回文子串，

3、初始化
都初始为false
4、遍历顺序
从下到上

class Solution {public int countSubstrings(String s) {int res = 0;char[] ss = s.toCharArray();if (s == null || (s.length() < 1)) return 0;boolean[][] dp = new boolean[ss.length][ss.length];for(int i=s.length()-1;i>=0;i--){for(int j=i;j<s.length();j++){if(ss[i]==ss[j]){if(Math.abs(i-j)<=1){dp[i][j] = true;res++;}else if(dp[i+1][j-1]==true){dp[i][j] = true;res++;}}else{dp[i][j] = false;}}}return res;}
}

二、最长回文子序列（力扣516）

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

分析：

回文子串是要连续的，回文子序列可不是连续的！
思路其实是差不多的，但本题要比求回文子串简单一点，因为情况少了一点。
1、确定dp数组以及下标含义
dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串，回文子串的长度最大为dp[i][j]

2、递推公式
分析两种情况：
如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。

加入s[j]的回文子序列长度为dp[i + 1][j]。
加入s[i]的回文子序列长度为dp[i][j - 1]。

那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

当s[i]与s[j]相等时：
dp[i][j] = dp[i+1][j-1] +2;

3、初始化
在对角线上的情况dp[i][j]应该是初始为1的。即：一个字符的回文子序列长度就是1。
其他情况dp[i][j]初始为0就行
4、遍历顺序
从下到上

class Solution {public int longestPalindromeSubseq(String s) {int[][] dp = new int[s.length()][s.length()];if(s==null || s.length()==0) return 0;//初始化for(int i=0;i<s.length();i++){dp[i][i] = 1;}//遍历顺序for(int i=s.length()-2;i>=0;i--){for(int j=i+1;j<s.length();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][s.length()-1];}
}

---