[数据结构与算法]十六、小节练手之动态规划（三）: 子序列问题

本文涉及到的问题都来源于：
力扣（LeetCode）
链接：https://leetcode-cn.com/problems

本文所涉及的算法思想参考自付东来的《labuladong的算法小抄》

1、子序列问题的两种思路

1、一个一维的dp数组
比如最长递增子序列中dp数组的含义为：
在子数组array[0…i]中，以array[i]为结尾的最长递增子序列的长度为dp[i]

2、一个二维的dp数组
1）涉及到两个字符串/数组时，dp数组的含义如下：
在子数组arr1[0…i]和子数组arr2[0…j]中，要求的子序列（最长公共自序列）长度为dp[i][j]
2）只涉及一个字符串/数组时，dp数组的含义如下：
在子数组arr[i…j]中，要求的子序列（最长回文子序列）的长度为dp[i][j]

2、最长回文子序列

516. 最长回文子序列
     给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
     子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
     输入：s = “bbbab”
     输出：4
     解释：一个可能的最长回文子序列为 “bbbb” 。

dp数组的定义为：在子串s[i…j]中，最长回文子序列的长度为dp[i][j]

class Solution:
    def longestPalindromeSubseq(self, s):
        # 定义并初始化dp_table
        n = len(s)
        dp_table = [[None for i in range(n)] for j in range(n)]

        # 填入base case的值
        for i in range(n):
            for j in range(n):
                if i > j:
                    dp_table[i][j] = 0
                elif i == j:
                    dp_table[i][j] = 1
        # 选择, 斜着计算方向斜着遍历
        for j in range(1, n):
            i = 0
            while max(i,j) < n:
                if s[i] == s[j]:
                    # print(dp_table)
                    # print(i,j)
                    dp_table[i][j] = dp_table[i+1][j-1]+2
                else:
                    dp_table[i][j] = max(dp_table[i][j-1], dp_table[i+1][j])
                i += 1
                j += 1

        return dp_table[0][n-1]