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:待定