代码随想录day40：动态规划part13

 647. 回文子串

class Solution {
    public int countSubstrings(String s) {
        char[] chars = s.toCharArray();
        int len = chars.length;
        boolean [][] dp = new boolean[len][len];
        int result = 0;
        for(int i = len - 1; i >= 0; i--){
            for(int j = i; j < len; j++){
                if(chars[i] == chars[j]){
                    if (j - i <= 1) { // 情况一 和 情况二
                        result++;
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) { //情况三
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return result;
    }
}

516. 最长回文子序列

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

原文地址：https://blog.csdn.net/qq_45890831/article/details/142995101

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！