【leetcode】5 最长回文子串 动态规划法

题目：
给你一个字符串 s，找到 s 中最长的 回文 子串。
分析：题目很简单，首先思路是遍历一下字符串的所有子串，判断一下是否是回文，然后再判断长度是不是最长的。

class Solution {
    public boolean isPalindrome(String z){
        for(int i=0;i<z.length();i++){
            //需要同时移动i和j,保证i和j是同时移动的
             if(z.charAt(i)!=z.charAt(z.length()-1-i))
            {
                return false;
            }
            //或者用这个
            
        }
        return true;
    }
    public String longestPalindrome(String s) {
        //寻找回文子串，需要保留原始字符的顺序。不能使用哈希表
        //使用双指针，移动指针进行遍历
        int i=0;
        int j=0;
        int maxi=0;
        int maxj=0;
        int maxl=0;
        
        for(i=0;i<s.length()-1;i++)
        {
            j=s.length()-1;
            while(!isPalindrome(s.substring(i,j+1)))
            {
                j--;
            }
            if(maxl<j-i+1){
                        maxi=i;
                        maxj=j;
                        maxl=j-i+1;
                    }
        }
        return s.substring(maxi,maxj+1);

    }
}

此思路需要注意的内容：此思路是暴力解法，时间复杂度较高
主要涉及到两个大块的循环思路：
1.获得字符串的子串（使用左右指针，固定左指针，逐渐移动右指针缩小子串长度、当子串为回文子串时停止此次循环，并移动左指针再次寻找）
2.·循环判断子串是否是回文串（按照回文子串的特性，需要从字符串的两头开始遍历、且需保证两头是同时移动的）

⚠️s.substring(a,b)方法是左闭右开

有没有时间复杂度更小的方法呢？——动态规划
1.什么是动态规划法
通过拆分问题、存储中间结果来得到最优解的方法。
四个步骤如下：

• 1.1.定义状态：定义子问题的解，通常用dp[i]（一维）或dp[i][j]（二维）等数组存储，例如dp[i]可表示 “前 i 个元素的最优解”。
• 1.2.确定状态转移方程：如何通过已知子问题的解推出更大子问题的解。
• 1.3.确定最小子问题的解（即无法再拆分的基础情况）
• 1.4.计算并存储结果
  2.动态规划法适用于什么样的问题：重叠子问题（问题的子问题之间存在重复)+最优子结构（问题最优解包含着子问题的最优解、可以通过子问题的最优解推导出原问题的最优解）
  3.那此问题是否符合动态规划法呢？
  重叠子问题：不同范围的子串判断依赖相同的更小的子串判断；
  最优子结构：最长回文子串的解依赖于更小的回文子串的解。（最）

基于以上信息分析本题：
1.定义状态：dp[i][j]表示i到j的字符串
2.状态转移方程：i到j的字符串为回文串i+1到j-1的字符串为回文串
3.最小子问题的解（边界情况）：当ij时，字符串肯定是回文串，或者i==i+1，字符串肯定是回文串。
代码为：

public class Solution {

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        char[] charArray = s.toCharArray();
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= len; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < len; i++) {
                //长度固定后，通过确定左边界，就可以得知右边界。即 j - i + 1 = L 
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= len) {
                    break;
                }

                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        //判断子串是否是回文串
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}

循环中的思路是：
1.最外层是子串的长度，从2一直到最长。长度为1的子串肯定是回文子串