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

题目： 

 

---

解析： 

状态表示：

 

---

状态转移方程： 

 

---

填表顺序： 

 

---

返回值： 

 

---

代码： 

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

原文地址：https://blog.csdn.net/robin_suli/article/details/145170432

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