S'S ALGORITHM

动态规划：回文（Palindromes）

概念引导

动态规划的回文问题有好几种比如：求一个字符串的最长子回文或者回文子串的数量，或一个字符串的回文子序列（可以不连续）的数量，或两个字符串的公共回文子串，或者两个字符串的公共回文子序列。

这里求一个字符串s中有多少种子回文。暴力破解的时间复杂度是O(n^3)，使用中心扩展法的时间复杂度是O(2*n^2)。

def longest(s):
    lenght = 0
    for i in range(len(s)):
        # odd length
        L, R = i, i
        while L > 0 and R < len(s) and s[L] == s[R]:
            length = max(length, R - L + 1)
            L += 1
            R -= 1

        # even length
        L, R = i, i + 1
        while L > 0 and  R < len(s) and s[L] == s[R]:
            length = max(length, R - L + 1)
            L += 1
            R -= 1
    return length

leetcodes

使用常规的中心扩展法求解即可。是一道求单个字符串的最长回文子串的问题。

和上一题没什么不同，仅仅是把求解变成了数数。

这是一道求最长回文子序列的题。单个字符串的。

求解最长回文子序列（Longest Palindromic Subsequence，简称LPS）的问题通常使用动态规划。基本的解题思路：

  1. 定义状态： 使用一个二维数组 dp，其中 dp[i][j] 表示字符串在区间 [i, j] 内的最长回文子序列的长度。

  2. 初始化状态： 对于长度为1的子序列，dp[i][i] = 1。对于长度为2的子序列，如果两个字符相等，dp[i][i+1] = 2；否则，dp[i][i+1] = 1。

  3. 状态转移： 使用递推公式来填充数组 dp，递推公式如下：

    dp[i][j] = dp[i+1][j-1] + 2             if s[i] == s[j]
dp[i][j] = max(dp[i+1][j], dp[i][j-1])  otherwise

    其中，s[i] 和 s[j] 分别表示字符串的第 i 和 j 个字符。

    这表示从i，j相等的段向两边各扩展一个长度，如果相等就长度加2，不想等则返回向左或者向右拓展一个长度后最长的那个。

  4. 遍历顺序： 为了确保在计算 dp[i][j] 时 dp[i+1][j-1] 已经被计算过，我们需要按照子序列长度递增的顺序以及从左到右的顺序遍历 i 和 j。也就是，沿着左下到右上的顺序。顺序应该如下索引[0, 2],[1, 3],[2, 4],[0, 3],[1, 4],[0, 4]。使用反向遍历，遍历步长然后取起点i就可以达到效果

  5. 结果： 最终的结果是 dp[0][n-1]，其中 n 是字符串的长度。

下面是一个简单的例子，使用字符串 “bbbab” 来说明：

  1. 创建一个二维数组 dp，其大小为 (5) x (5)。
   0 1 2 3 4
  -----------
0 | 0 0 0 0 0
1 | 0 0 0 0 0
2 | 0 0 0 0 0
3 | 0 0 0 0 0
4 | 0 0 0 0 0
  1. 初始化长度为1和2的子序列。
   0 1 2 3 4
  -----------
0 | 1 2 0 0 0
1 | 0 1 2 0 0
2 | 0 0 1 1 0
3 | 0 0 0 1 1
4 | 0 0 0 0 1
  1. 使用递推公式填充数组 dp。
   0 1 2 3 4
  -----------
0 | 1 2 3 3 4
1 | 0 1 2 2 3
2 | 0 0 1 1 3
3 | 0 0 0 1 1
4 | 0 0 0 0 1
  1. 最终结果是 dp[0][4]，即 4，这表示 “bbbab” 的最长回文子序列的长度为 4。

小感想：一天一道题好好解出来，好过做一堆不知道做了什么！