算法笔记|Day40动态规划XIII

☆☆☆☆☆leetcode 647. 回文子串

题目链接：leetcode 647. 回文子串

题目分析

1.dp数组含义：dp[i][j]表示表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串；
2.递推公式：if(s.charAt(i)==s.charAt(j))：if(j-i<=1)dp[i][j]=true;else if(dp[i+1][j-1])dp[i][j]=true;（若i位置元素与j位置元素不同，一定不是回文子串，无需操作；只需要考虑i位置元素与j位置元素相同时，即s.charAt(i)==s.charAt(j)。在此基础上，若下标i与j相同或差为1，是回文子串；若下标i与j相差大于1，看i到j区间是不是回文子串就看i+1与j-1区间；如果是回文子串，res加一）；
3.初始化：所有dp[i][j]=false；
4.遍历顺序：i从大到小，j从小到大，而且j大于等于i，j从i开始。

代码

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){
                        dp[i][j]=true;
                        res++; 
                    }else if(dp[i+1][j-1]){
                        dp[i][j]=true;
                        res++;                        
                    }                    
                }
            }
        }
        return res;
    }
}

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

题目链接：leetcode 516.最长回文子序列

题目分析

1.dp数组含义：dp[i][j]表示字符串s在[i, j]范围内最长的回文子序列的长度；
2.递推公式：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])（若i位置元素与j位置元素相同，回文子序列长度在dp[i+1][j-1]基础上加二；若i位置元素与j位置元素不同时，取[i+1, j]与[i, j-1]两个区间最长回温子序列的最大值）；
3.初始化：所有dp[i][i]=1；
4.遍历顺序：i从大到小，j从小到大，而且j大于等于i，j从i+1开始。

代码

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];
    }
}