day56

1、leetcode647 回文子串

1. 动规五部曲

   1. 是否是回文子串，如果是dp[i] [j]为true，否则为false

   2. 递推公式

      1. s[i] == s[j]

      2. 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串

      3. 情况二：下标i 与 j相差为1，例如aa，也是回文子串

      4. 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1] [j - 1]是否为true。

         if (s[i] == s[j]) {
             if (j - i <= 1) { // 情况一 和 情况二
                 result++;
                 dp[i][j] = true;
             } else if (dp[i + 1][j - 1]) { // 情况三
                 result++;
                 dp[i][j] = true;
             }
         }
         

         result就是统计回文子串的数量。

      5. s[i] != s[j]

      • dp[i] [j] = false
      3. 代码中没有列出当s[i]与s[j]不相等的时候，因为在下面dp[i] [j]初始化的时候，就初始为false。

   3. 初始化

      • 初始化为false

   4. 遍历顺序

      • 从下到上、从左到右

   5. 举例

2. 代码

   class Solution {
       public int countSubstrings(String s) {
           boolean[][] dp = new boolean[s.length()][s.length()];
           int res = 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(j-i<=1) {
                           res++;
                           dp[i][j] = true;
                       } else if (dp[i+1][j-1] == true) {
                           res++;
                           dp[i][j] = true;
                       }
                   }
               }
           }
   
           return res;
       }
   }
   

2、leetcode516 最长回文子序列

1. 动规五部曲

   1. dp[i] [j]：表示区间范围[i,j] （注意是左闭右闭）的子串的最长的回文子序列的长度
   2. 递推公式
      1. s[i] == s[j]
      • dp[i] [j] = dp[i+1] [j-1] + 2
      2. s[i] != s[j]
      • dp[i] [j] = dp[i+1] [j]
      • dp[i] [j] = dp[i] [j-1]
      • dp[i] [j] = max(dp[i+1] [j] , dp[i] [j-1])
   3. 初始化
      1. i与j相同，那么dp[i][j]一定是等于1的，即：一个字符的回文子序列长度就是1。
      2. 其他情况dp[i][j]初始为0
   4. 遍历顺序
      • 从下到上、从左到右
   5. 举例

2. 代码

   class Solution {
       public int longestPalindromeSubseq(String s) {
           int[][] dp = new int[s.length()][s.length()];
           for(int i=0; i<s.length(); i++) dp[i][i] = 1;
   
           for(int i=s.length()-1; 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+1][j] , dp[i][j-1]);
                   }
               }
           }
   
           return dp[0][s.length()-1];
   
       }
   }