动态规划回文串问题系列一＞回文子串

用户11305962

发布于 2025-01-13 08:34:47

5100

代码可运行

文章被收录于专栏：学习学习

运行总次数：0

代码可运行

题目：

解析：

注意：字串和子数组差不多

状态表示：

状态转移方程：

初始化：

填表顺序：

返回值：

返回dp表里true的个数

代码：

public int countSubstrings(String ss) {
        char[] s = ss.toCharArray();
        int n = s.length;
        boolean[][] dp = new boolean[n][n];
        int count = 0;

        for(int i = n-1; i >= 0; i--){
            for(int j = i; j < n ; j++){ 
                /** 
                if(i == j) dp[i][j] = true;//同一个位置
                else if(i+1 == j) dp[i][j] = true;//相邻位置
                else dp[i][j] = dp[i+1][j-1];//i和j之间找
                */ 

                if(s[i] == s[j])
                    dp[i][j] = i+1 < j ? dp[i+1][j-1] : true;
                if(dp[i][j] == true) count++;
            }
        } 

        return count;
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-01-05，如有侵权请联系 cloudcommunity@tencent.com 删除

dp