Java数据结构与算法(最长回文子串动态规划)

前言

动态规划主要用于解决具有重叠子问题和最优子结构性质的问题。它通过将问题分解为子问题来解决复杂问题，每个子问题仅解决一次，并将其结果存储，以供后续使用，从而避免了重复计算。

动态规划的基本思想

1. 分解问题：将问题分解为子问题，这些子问题的解决方案可以组合成原问题的解决方案。
2. 识别最优子结构：问题的最优解包含其子问题的最优解。
3. 存储中间结果：使用一个数组或表格来存储已经解决的子问题的结果，以避免重复计算。

动态规划的步骤

1. 定义子问题：确定如何将原问题分解成子问题。
2. 递推公式：找到子问题之间的关系，形成递推公式（状态转移方程）。
3. 边界条件：确定最小子问题的解（边界条件）。
4. 填表格：根据递推公式和边界条件，从小问题开始逐步计算出大问题的解。

实现原理

这里定义最长回文子串长度的大小为maxLen，起点位置为0.

初始化:dp[i][i]=true;

转移方程：charArray[i]=charArray[j]&&dp[i+1][j-1]

边界条件:

(j-1)-(i+1)+1<2=>j-i<3.

具体代码实现

package test14;

class Solution {
    public String longestPalindrome(String s) {
        int len=s.length();
        if(len<2){
            return s;
        }
        int maxLen=1;
        int begin=0;
        boolean[][] dp=new boolean[len][len];
        for(int i=0;i<len/2;i++){
            dp[i][i]=true;
        }
        char[] charArray=s.toCharArray();
        for(int j=1;j<len;j++){
            for(int i=0;i<j;i++){//i从小开始，j从大开始
                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];
                    }

                }
                if(dp[i][j]&&j-i+1>maxLen){
                    maxLen=j-i+1;
                    begin=i;
                }
            }
        }
        return s.substring(begin,begin+maxLen);

    }

    public static void main(String[] args) {
        Solution solution=new Solution();
        System.out.println(solution.longestPalindrome("cbaabd"));
    }



}

QA:待定