算法打卡：第九章 动态规划part13

今日劳绩：回文子串，最长回文子序列

1. 回文子串

标题链接：647. - 力扣（LeetCode）
思路：
（1）dp数组的界说不再是标题的要求，而是二维的，下标 i 和 j 表示字符串对应下标的子串是不是回文串。再使用变量记录回文子串的个数
（2）初始化全为0
（3）如果当前两个字符相等，判定长度是否为0或1，满足要求则都是回文子串；如果长度大于1，那么下标向中间聚拢，如果仍然是回文子串，记录个数。
（4）遍历次序：依据递推公式，需要下标向中间聚拢也就是左下角的值推出当前值，所以需要从上到下从左到右遍历。
方法：

1. class Solution {
2.     public int countSubstrings(String s) {
3.         int len=s.length();
4.         int result=0;
6.         // 字符串中从 i 到 j 的子串是不是回文串
7.         boolean[][] dp=new boolean[len][len];
9.         // 初始化
10.         for (int i=0;i<len;i++){
11.             for (int j=0;j<len;j++){
12.                 dp[i][j]=false;
13.             }
14.         }
16.         // 从底向上，从左到右
17.         for (int i=len-1;i>=0;i--){
18.             for (int j=i;j<len;j++){
19.                 if (s.charAt(i)==s.charAt(j)){
20.                     if (j-i<=1){
21.                         dp[i][j]=true;
22.                         result++;
23.                     }else {
24.                         dp[i][j]=dp[i+1][j-1];  // 向中间靠拢
25.                         if (dp[i][j]==true){
26.                             result++;
27.                         }
28.                     }
29.                 }
30.             }
31.         }
33.         return result;
34.     }
35. }

复制代码

2. 最长回文子序列

标题链接：516. - 力扣（LeetCode）
思路：
（1）dp数组表示 i 和 j 下标范围内的最长回文子序列长度
（2）初始化：递推公式不包罗长度为1的回文子串，所以二维数组的对角线元素全为1
（3）递推公式：如果 i 和 j 下标上的字符相等，那么回文子序列的长度在内层子串的基础上加2；如果不相等，则取分别加上左边的字符和右边的字符中的最大值。
（4）遍历次序：从递推公式可以看出来，当前位置依靠于左，左下，下的元素值，所以是从下到上，从左到右遍历。
方法：

1. class Solution {
2.     public int longestPalindromeSubseq(String s) {
3.         int len=s.length();
5.         // 设置为len+1，初始化较为简单
6.         int[][] dp=new int[len+1][len+1];
8.         for (int i=len-1;i>=0;i--){
9.             dp[i][i]=1;
10.             for (int j=i+1;j<len;j++){
11.                 if (s.charAt(i)==s.charAt(j)){
12.                     dp[i][j]=dp[i+1][j-1]+2;
13.                 }else {
14.                     dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
15.                 }
16.             }
17.         }
19.         return dp[0][len-1];
20.     }
21. }

复制代码

总结：
（1）子序列和子串的区别在于，子序列可以删除元素，如果可以删除的环境不止一个就需要取此中的最大值。
（2）如果不能确定遍历次序，可以根据递推公式，分析dp数组中当前位置的值由哪些方向的值推导出来。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。