代码随想录day 57 动态规划模块 回文子串,最长回文子序列

文章目录

• • 1.leetcode 647. 回文子串
  • • • 1.1 详细思路及解题步骤
      • 1.2 Java版代码示例
  • 2.leetcode 516. 最长回文子序列
  • • • 2.1 详细思路及解题步骤
      • 2.2 Java版代码示例

1.leetcode 647. 回文子串

1.1 详细思路及解题步骤

  该题用动态规划的思路解题，注意回文子串是原字符串中连续的部分，一个字母的也是回文子串，直接就用动态规划的做题步骤进行分析。

   1.确定dp数组以及下标的含义

这里dp数组的含义一般就是题目需要求的东西
也就是说这题dp[i][j] (Boolean数组)代表的就是s[i,j]左闭右闭的区间中的子串是否为回文子串，是就true，不是就false。

   2. 确定递推公式

• s[i]与s[j]不相等，就是false
• s[i]与s[j]相等
   - 且i-j<=1,也就是只有一个或者两个子串，这时dp[i][j]=true;
   - 当i-j>1时候，如果dp[i+1][j-1]=true时，那就可以考虑这个dp[i][j]=true;

  3. dp数组的初始化问题

不需要初始

  4.确定遍历顺序

当i-j>1时候，如果dp[i+1][j-1]=true时，这时候的dp[i][j]是由dp[i+1][j-1]推导出来的，所以i是倒序遍历，j是顺序遍历

  5.推导dp数组

1.2 Java版代码示例

class Solution {public int countSubstrings(String s) {if(s.length()==0) return 0;boolean[][] dp=new boolean[s.length()][s.length()];int result=0;for(int i=s.length()-1;i>=0;i--){for(int j=i;jif(s.charAt(i)==s.charAt(j)){if(j-i<=1){result++;dp[i][j]=true;}else if(dp[i+1][j-1]){result++;dp[i][j]=true;}}else{dp[i][j]=false;}//    if(s.charAt(i)==s.charAt(j)&&(j-i<=1||dp[i+1][j-1])){//        result++;//        dp[i][j]=true;//    }else{//        dp[i][j]=false;//    }}}return result;}
}

2.leetcode 516. 最长回文子序列

2.1 详细思路及解题步骤

  这题跟上题不同的是这题并不是连续的，还是按照动态规划的思路分析。

   1.确定dp数组以及下标的含义

dp[i][j]表示s[i，j]范围内的最长子序列长度

   2. 确定递推公式

• 当s[i]与是s[j]相等时，dp[i][j]=dp[i-1][j-1]+2
• 当s[i]与是s[j]不相等时
  - 去掉s[i],dp[i][j]=dp[i+1][j]
  - 去掉s[j],dp[i][j]=dp[i][j-1]

  3. dp数组的初始化问题

dp[i][i]初始为1，其他初始为0

  4.确定遍历顺序

去掉s[i],dp[i][j]=dp[i+1][j]，这里确定遍历顺序，i倒序，j顺序

  5.推导dp数组

2.2 Java版代码示例

public class Solution {public int longestPalindromeSubseq(String s) {int len = s.length();int[][] dp = new int[len][len];for (int i = len - 1; i >= 0; i--) { // 从后往前遍历 保证情况不漏dp[i][i] = 1; // 初始化for (int j = i + 1; j < len; 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 + 1][j],dp[i][j - 1]);}}}return dp[0][len - 1];}
}