描述

最长回文子列（非字串， dp遍历方向) - 图1

反向遍历

  1. # input: abcda   output: 3(aca)
  3. def MaxPalindromixSub(s: str):
  4.     # dp[i][j] s[i, j]闭区间内的最长回文子列，
  5.     # 注意dp数组遍历的方向
  7.     dp = [[0 if i != j else 1 for j in range(len(s))] for i in range(len(s))]
  8.     for row in dp:
  9.         print(row)
  11.     # 反向遍历： 从最后一行开始
  12.     for i in range(len(s) - 1, -1, -1):
  13.         for j in range(i + 1, len(s)):
  14.             if s[i] == s[j]:
  15.                 dp[i][j] = 2 + dp[i + 1][j - 1]
  16.             else:
  17.                 dp[i][j] = max(
  18.                     dp[i][j - 1],
  19.                     dp[i + 1][j]
  20.                 )
  21.     for row in dp:
  22.         print(row)
  24. if __name__ == '__main__':
  25.     MaxPalindromixSub('aba')
  • base case

[1, 0, 0]
[0, 1, 0]
[0, 0, 1]

  • output

[1, 1, 3]
[0, 1, 1]
[0, 0, 1]

斜着遍历

  1.     # 斜着遍历， 替换上面的双重for, 结果是一样的.
  2.     for k in range(1, len(s)):  # 第几斜【1，】 主对角线是base case 不用遍历
  3.         j = k  # 初始化 列标
  4.         for i in range(0, len(s) - k):
  5.             if s[i] == s[j]:
  6.                 dp[i][j] = 2 + dp[i + 1][j - 1]
  7.             else:
  8.                 dp[i][j] = max(
  9.                     dp[i][j - 1],
  10.                     dp[i + 1][j]
  11.                 )
  12.             j = j + 1

总结

  • dp数组的遍历方向可能不同 正的 反的 斜的

    • 可以根据base base 来分析

  • 还可以根据最长公共子列的方法来分析（正序， 倒序）