动态规划

文章目录

1. 1. 7.2 LCS 最长公共子序列
2. 2. Side Notes

DP广泛用于求解组合最优化问题。动态规划(Dynamic Tabling)不是递归调用自身，但是问题的基础解通常以递归函数的形式予以说明的。递归是自顶向下，动态规划是自底向上。

• 用来引出递归和归纳的最常见的例子是 斐波那契数列问题

每一个数都是前两个数的和

procedure f(n)
	if(n==1) or (n==2): return 1
	else: return f(n-1) + f(n-2)

但是如果自底向上明显能够在n的时间和常数空间

• 另一个类似的例子是二项式系数 $$(_k^n) = (_{k-1}^{n-1}) + (_k^{n-1})$$ 如果自顶向下需要的时间复杂度为指数时间复杂度 $O(2^n)$,但是通过构造帕斯卡三角形，能够很快地计算出来。

7.2 LCS 最长公共子序列

在字母表Σ上，分别给出两个长度为m和n的字符串A 和 B，确定在A和B中最长公共子序列的长度。A=”a1a2…Am” B=’b1b2..bn’

为了使用动态规划技术，我们首先寻找一个最长公共子序列长度的递推公式

L[i, j] = L[i-1, j-1] + 1 if ai==bj

L[i,j] = max{L[i-1, j], L[i, j-1]} if ai!=bj

algorithm 7.1 LCS
inputs: A, B (n, m)
outputs: A B的LCS的长度

for i = 0->n:
	L[i, 0] = 0
for j = 0->m:
	L[0, j] = 0
for i = 1->n:
	for j = 1 -> m:
		if ai == bj:
			L[i, j] = L[i-1, j-1] + 1
		else:
			L[i, j] = max(L[i-1, j], L[i, j-1])
return L[n, m]

如何输出 最长公共子序列？

最长公共子序列可能是有多种长度相同的子序列！！！，如何找出所有的子序列。一个子序列也可能以不同的下标序列出现！

如何找出所有的LCSs?

Side Notes

在DP问题中，也可以利用递归的形式达到DP的时间复杂度。这种递归使用了一张备忘录以记录已被计算过的情况，以避免重叠case的重复调用，因此被称为带备忘录的递归。 —-《算法导论》