动态规划-LIS

LIS 最长递增子序列

如

x = [10, 9, 7, 21, 18, 3, 42, 30, 79, 101, 20]

x 的 最长递增子序列长度为5

10/9/7      21/18     42/30     79     101

方法一

1. 对 x 排序（升序）生成 x_sorted
2. 对 x 和 x_sorted 执行 LCS 操作即可

import copy

# LCS
def dp(i, j):
    if i == -1 or j == -1:
        return 0
    if x[i] == y[j]:
        return dp(i-1, j-1) + 1
    return max(dp(i-1, j), dp(i, j-1))

x = [10, 9, 7, 21, 18, 3, 42, 30, 79, 101, 20]
y = copy.copy(x)
y.sort()
print(dp(len(x)-1, len(y)-1))

方法二

动态规划思维

421620444545_.pic_hd.jpg

T = []
def method2(lis):
    for index, i in enumerate(lis):
        if not T:
            T.append(1)
            continue
        item_max = 1
        for j_index, j_max in enumerate(T):
            if i > lis[j_index]:
                item_max = max(item_max, T[j_index]+1)
        T.append(item_max)

method2(x)
print(T)
print(max(T))

[1, 1, 1, 2, 2, 1, 3, 3, 4, 5, 3]
5

方法三

help = []
for item in x:
    if not help:
        help.append(item)
        continue
    if item > help[-1]:
        help.append(item)
    else:
        index = bisect.bisect_left(help, item)
        help[index] = item
print(help)

[3, 18, 20, 79, 101]