动态规划——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);
    }