以动态规划的方式求解最长回文子串_动态规划求最长回文子串

Dynamic Programming (DP) is an algorithmic technique for simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its subproblems.

以递归的方式将复杂问题分解为“更简单的子问题”：整体问题的最优解取决于其子问题的最优解

leetcode - 5. 最长回文子串
官方动态规划的题解写很抽象，没一个图片，看的差点怀疑智商，后看到如下视频，清楚多了，遂记录下来
使用【动态规划】求解最长回文子串

判断方式：首尾字符比较，之后去掉首尾字符，再比较现有首尾字符。单个字符一定是一个字串

暴力解法状态无法保留，比如[a,b,c,a]中，首尾字符相等，再比较[b,c]，但[b,c]可能之间已经比较过了，现在又需要重新比较下

使用动态规划如下图，注意，这里的二维数组要理解为区间，如 [3,5] 为区间 [b,a,b]

var longestPalindrome = function (s) {
   
  let n = s.length
  let dp = new Array(n).fill(0).map(() => new Array(n).fill(true))
  for (let i = n - 2; i >= 0; i--) {
   	// 第一个[b]一定为true，所以从[a,b]开始
    for (let j = i + 1; j < n; j++) {
   		// 这里的二维数组理解为区间，如[3,5]为区间[b,a,b]
      dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1]	// 起点和端点相同，并且内部字串起点和端点也相同，代表是回文子串		[i+1,j-1]代表内部
    }
  }
  let maxstr = ""
  for (let i = 0</
1
2
3
4
5
6
7
8
9
10
11
12