动态规划1

SRTBOT框架

Subproblem definition 子问题定义

用清晰的语言去定义一个子问题是什么，并明确它所包含的参数。
子问题通常是原问题输入的一部分，有时候为了记录局部状态，我们还需要引入一些辅助变量。

Relate subproblem solutions recursively 写出递归关系式

找到当前子问题和更小子问题之间的数学或逻辑关系。
这是最难的一步，需要我们发挥归纳思维。我们可以尝试一个局部暴力破解。也就是问自己一个问题：“如果我知道了关于这个子问题的某个关键决策，它会缩减成哪个更小的子问题？”然后把所有可能的决策都试一遍，从中跳出最好的那个。

Topological order on subproblems 确定拓扑顺序

递归调用其实可以看做是一个有向图，如果算法能够正常结束，这个依赖图必然是一个有向无环图。
我们需要清晰的指出子问题的计算顺序，以确保当我们在计算当前子问题的时候，它所依赖的更小的子问题已经被计算出来了。

Base cases of relation 边界条件

当子问题足够小，不再依赖更小的子问题时，可以直接给出答案的情况。
比如数组索引为空，越界，或 n=0 之类的时刻，必须处理好边界，否则程序会进入死循环。

Original problem solution via subproblems 原问题的解

明确定义原问题的最终答案是如何通过我们算出来的子问题得到的。
有时候原问题的解就是某一个特定的子问题；有时候是所有子问题中的最值。此外，如果题目不仅让你求一个最值，还让你输出具体路径，这一步通常由父节点指针来回溯恢复出完整解。

Time analysis 时间复杂度分析

计算整个算法的时间消耗。
在动态规划中，总时间的通用公式是 $\text{总时间}=\sum_{x\in X} work(x)$ 简单来说，如果每个子问题内部做非递归工作，那么总时间=子问题的个数*每个子问题的内部花费

斐波那契数列的进化

我们按照上面的框架来拆解一下 Fibonacci 数列的求解

S：F(i)表示第 i 个 Fibonacci 数，其中 $i\in\{0,1,\dots,n\}$ 。
R：根据定义，我们有 $F(i)=F(i-1)+F(i-2)$ 。
T：按照 i 的递增序列。
B：最开始我们知道 F(0) = 0, F(1) = 1
O：我们需要的是 F(n)
T：如果我们直接采用普通的递归，那么将会是指数级的时间复杂度，这是因为我们对同一个子问题反复计算了多次这是一种极大的浪费！

我们有两个方案来优化这样的算法

方案A：自顶向下+备忘录

我们可以利用一个表格记录已经计算过的值，这样就避免了重复计算

def fib(n):
	memo = {}
	def F(i):
		if i < 2:
			return i
		if i not in memo:
			memo[i] = F(i-1) + F(i-2)
		return memo[i]
	return F(n)

方案B：自底向上递推

我们既然已经知道了拓扑排序是 i 逐渐增大，那么可以干脆用循环从 base case 开始计算，彻底放弃递归

def fib(n):
	F = {}
	F[0], F[1] = 0, 1
	for i in range(2,n+1):
		F[i] = F[i-1] + F[i-2]
	return F[n]

保龄球最大得分问题

情景：

一排有 n 个保龄球销，从左到右标记为 0，1，…，n-1

每个球都有一个分值 $v_i$
每次扔球有两种选择：
- 只击中一个销 $i$ ，获得 $v_i$ 分
- 击中 2 个相邻的销 $i$ 和 $i+1$ ，获得两数乘积 $v_i\cdot v_{i+1}$ 分
被击中的销就会被移除，不能再打。
目标：扔出任意次数的球，最大化你的得分。

我们继续采用SRTBOT框架进行思考

S：B(i) 表示只考虑第 i 个到最后一个销时能获得的最高得分。
R：现在我们站在第 i 个销面前，我们有三种可能的选择：1. 直接跳过第 i 个销，不打它，原问题变为从第 i+1 个销开始打，得分为 $B(i+1)$ 2. 只打第 i 个销，获得 $v_i$ 分，原问题缩减为从第 i+1 个销开始打，得分为 $B(i+1)+v_i$ 3. 把 i 和 i+1 一起打掉，获得 $v_i\cdot v_{i+1}$ 分，原问题变为从第 i+2 个销开始打，得分为 $B(i+2)+v_i\cdot v_{i+1}$
T：观察上面的情况，我们知道，计算 $B(i)$ 需要提前知道 $B(i+1)$ 和 $B(i+2)$
B：当销不够大的时候 $B(n)=0,B(n+1)=0$ 后者用于防止越界
O：我们需要的是 $B(0)$
T：子问题共有 $\Theta(n)$ 个，每个子问题内部工作量为 $\Theta(1)$ ，所以总的时间复杂度为 $\Theta(n)$

我们可以用代码实现如下

def bowl(v):
	n = len(v)
	B = {}
	B[n] = 0
	B[n+1] = 0
	for i in reversed(range(n)):
		B[i] = max(
		B[i+1],
		v[i] + B[i+1],
		v[i] * v[i+1] + B[i+2]
		)
	return B[0]