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

用户11305962

发布于 2025-01-17 14:12:16

6400

代码可运行

文章被收录于专栏：学习

运行总次数：0

代码可运行

题目：

解析：

状态表示：

状态转移方程：

填表顺序：

返回值：

代码：

public int longestPalindromeSubseq(String ss) {
        char[] s = ss.toCharArray();
        int n = s.length;
        int[][] dp = new int[n][n]; 

        //根据状态转移方程：合并后的写法
        // for(int i = n-1; i >= 0; i--){
        //     for(int j = i; j < n; j++){
        //         if(s[i] == s[j]){
        //             if(i == j) dp[i][j] = 1;
        //             else if(i+1 == j) dp[i][j] = 2;
        //             else if(i+1 < j) dp[i][j] = dp[i+1][j-1]+2;
        //         }
        //         else dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]);
        //     }
        // }


        for(int i = n-1; i >= 0; i--){
            dp[i][i] = 1;
            for(int j = i+1; j < n; j++){
                if(s[i] == s[j])
                    dp[i][j] = dp[i+1][j-1]+2;
                else dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]);
            }
        }

        return dp[0][n-1];
    }

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

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

math