5. 最长回文子串

202409112305 动态规划很多时候就是在填表

1. 暴力解法
2. 动态规划
3. 马拉车算法，没仔细看

动态规划算法：

func longestPalindrome(s string) string {
    return dynamic(s)    
}

func dynamic(s string) string {

    dp := make([][]bool, len(s))

    for i := range dp {
        dp[i] = make([]bool, len(s))
        dp[i][i] = true
    }

    ret := s[0:1]
    mxLen := 1
    for j := 1; j < len(s); j++ {
        for i := 0; i<j; i++ {
            if s[i] == s[j] {
                if j-i < 3 {
                    dp[i][j] = true
                } else {
                    dp[i][j] = dp[i+1][j-1]
                }
                if dp[i][j] && j-i+1 > mxLen {
                    mxLen = j-i+1
                    ret = s[i:j+1]
                }
            } else {
                dp[i][j] = false
            }
        }
    }

    return ret
}

初始化：

填表格，对角线，也就是 i=j 时，单个字符，都是回文串，设置为 true dp[i][i] = true

遍历顺序：

因为初始化的是对角线，也就是如图所示：
图中对角线坐标写错了，应该是 [0,0] [1,1] [2,2] [3,3]

如果按照平常的顺序，这么写代码遍历

for i := 0; i < len(s); i++ {
	for j := i+1; j<len(s); j++ {
		...
	}
}

那么会有如图所示的问题，[0,3] 会因为需要 [1,2] 的结果从而导致无法推算出正确的结果

所以需要这么遍历，就能够使用到上一列的数据