个人博客：动态规划第二讲：线性DP

线性 DP 问题是指递推方程具有明显的线性关系，有一维线性和二维线性。

数字三角形

问题描述

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

输入样例：

5  # 三角形的行数
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

输出样例：

30

问题分析

我们从集合的角度来对该问题进行分析：

注意：

在进行状态计算的时候有两个关键点：

1. 每行的第一个元素只能从右上转移过来；
2. 每行的最后一个元素只能从左上转移过来。

因此需要单独将这两种情况拿出来考虑。

问题求解

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
inf = float("-inf")
dp = [[inf] * (n) for i in range(n)]
dp[0][0] = a[0][0]
for i in range(1, n):
    for j in range(i+1):
        if j == 0:
            dp[i][j] = dp[i-1][j] + a[i][j]
        elif j == i:
            dp[i][j] = dp[i-1][j-1] + a[i][j]
        else:
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j]
print(max(dp[n-1]))

最长上升子序列

问题描述

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

问题分析

从集合的角度来进行分析：

我们按照第 i 个元素结尾的上升子序列的前一个元素来进行集合的划分，前一个元素可以是空，也可以是第 1 个元素，一直到第 i-1 个元素，因此一共划分为 i 个集合。状态转移方程为：

dp[i] = 1 # 前一个元素为空
for j in range(1, i):
    if a[j] < a[i]:
        dp[i] = max(dp[i], dp[j]+1)

问题求解

n = int(input())
a = list(map(int, input().split()))
dp = [0] * n
for i in range(n):
    dp[i] = 1
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))

最长公共子序列

问题描述

给定两个长度分别为 N 和 M 的字符串 A 和 B ，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

输入样例：

4 5
acbd
abedc

输出样例：

3

问题分析

由于涉及到两个字符串，所以需要用二维状态表示 f[i, j] ，其分析图如下：

本题的重点是在集合的划分，假定两个字符串分别为 a 和 b ，则可以根据子序列是否包含 a[i] ，b[j] 将集合划分为四种情况：

1. 子序列不包含 a[i] 和 b[j] ，用 00 表示，其对应了状态表示 f[i-1, j-1]
2. 子序列包含 b[j] ，但不含 a[i] ，用 01 表示；
3. 子序列包含 a[i] ，但不含 b[j] ，用 10 表示；
4. 子序列包含 a[i] 和 b[j] ，用 11 表示，其对应了状态表示 f[i-1, j-1]+1

关键点是如何计算中间两种的状态表示，因为 f[i-1, j] 表示的集合是包含 01 部分的集合，且被整个集合 f[i, j] 包含的，而且我们是求 f[i, j 中的最大值，因为我们完成可以将 01 部分的集合放大为 f[i-1, j] ，并不影响我们的最大值。同理，10 部分的集合就对应了状态表示 f[i][j-1] 。

同时我们可以发现 f[i-1, j] 是包含 f[i-1, j-1] 的，且 11 成立的条件是 a[i] == b[j] 。

动态规划问题求最大值和最小值是集合可重复的，但不能漏元素。

问题求解

n, m = map(int, input().split())
a = input()
b = input()

dp = [[0] * (m+1) for i in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # 01 和 10 的情况
        if a[i-1] == b[j-1]:  # 11 的情况
            dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1)
print(dp[n][m])