关于算法:动态规划系列-线性DP之LIS与LCS

最长回升子序列

给定一个无序的整数数组，找到其中最长回升子序列的长度。

例如对于 [10,9,2,5,3,7,101,18] 返回 4。

思考第 i 位数字 nums[i]是否能够继承之前的状态，须要晓得之前状态子序列的长度 n 与最右值 m。如果 nums[i]大于 m，状态 i 的长度为 n +1，最右值为 nums[i]。

上述的动静布局过程能够用一维数组记录中间状态，对于 status[i]记录了以 nums[i]为子序列最初一个元素的子序列长度。status[i]的计算须要遍历之前的所有状态，取最大长度。

def solution(nums):
    if not nums: return 0
    status = [1]*len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]: status[i] = max(status[i], status[j]+1)
    return max(status)

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

例如对于 text1 = “abcde”，text2 = “ace” 返回 3。

思考对于中间状态 (i, j)，text1[i] 与 text2[j]的退出是否对已有状态产生了影响。

1. text1[i]与 text2[j]的退出对已有状态无影响，状态(i, j) = 状态(i-1, j-1)。
2. text1[i]与 text2[j-1]匹配，状态(i, j) = 状态(i, j-1)。
3. text2[j]与 text1[i-1]匹配，状态(i, j) = 状态(i-1, j)。
4. text1[i] == text2[j]，text[i]与 text[j]匹配，状态(i, j) = 状态(i-1, j-1) + 1。

上述的动静布局过程能够用二维数组记录中间状态，对于 status[i][j]记录了 text[:i]与 text[:j]的最长公共子序列的长度。status[i][j]的计算依赖于 status[i-1][j]，status[i][j-1]，status[i-1][j-1]。

def solution(text1, text2):
    n, m = len(text1), len(text2)
    status = [[0]*(m+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, m+1):
            status[i][j] = max(status[i-1][j], status[i][j-1])
            if text1[i-1] == text2[j-1]:
                status[i][j] = max(status[i][j], 1 + status[i-1][j-1])
    return status[n][m]

对于状况 1，曾经蕴含在 status[i-1][j]或 status[i][j-1]中。