动态规划——leetcode5、最长回文子串

1、题目描述：

2、解题方法：动态规划

　　动态规划解题步骤：

　　　　1、确定状态

最后一步：如果s[i,...,j]是回文子串，那么需要满足两个条件

　　　　　　　　① s[i] == s[j]；

　　　　　　　　② s[i+1,...,j-1]是回文子串；

子问题：我们要验证s[i+1,...,j-1]是不是回文子串
用dp[i][j]来表示s[i,...,j]是不是回文子串

　　　　2、转移方程

　　　　　　dp[i][j] = （s[i] == s[j]）&& dp[i+1][j-1]

　　　　3、初始条件和边界情况

　　　　　 初始条件：dp[i][i] == true;

　　　　　　边界条件：在s[i] == s[j]的条件下，j-i<=2或者j-i<3，即说明s[i,...,j]的长度为2或者是3时，不用检查是不是回文串。

　　　　　　

　　　　4、计算顺序

　　　　　以字符串s:babab为例，一列一列的进行填表，先升序填列，再升序填行。

　　　　　　　

3、代码：

public String longestPalindrome(String s) {

        int len = s.length();

        if(len < 2){

            return s;

        }

        int maxLen = 1;

        int start = 0;

        char[] res = s.toCharArray();

        boolean[][] dp = new boolean[len][len];

        for(int i = 0; i < len; i++){

            dp[i][i] = true;

        }

        for(int j = 1; j < len; j++){

            for(int i = 0; i < j; i++){

                if(res[i] == res[j]){

                    if(j - i < 3 || dp[i+1][j-1] == true){

                        dp[i][j] = true;

                    }

                    if( j-i+1 > maxLen && dp[i][j] == true){

                        maxLen = j-i+1;

                        start = i;

                    }

                }

            }

        }

        return s.substring(start,start + maxLen);

    }

动态规划——leetcode5、最长回文子串的相关教程结束。