动态规划(DP)基础（一）
1、动态规划简介
? 按照MIT算法课6.006中的说法，动态规划是一种用空间换时间的策略，即DP=recursion+memorization。本系列DP博客将以MIT算法课6.006中的实例为基础，以初学者的视角对一些特别且有价值的实例进行算法分析与代码实现。
2、一个简单例子——斐波那契数列
? 没有什么比斐波那契数列更适合初学者学习以入门动态规划。动态规划可能是很多初学者入门递归算法的重要例子，下面的代码给出了基于python的最简洁的斐波那契数列递归算法。
def Fibonacci(i):
if (i == 1) | (i == 2):
return 1
return Fibonacci(i - 1) + Fibonacci(i - 2)
? 简单分析上述算法，不难发现其算法复杂度为（求斐波那契数列第n位的值）：
θ
(
2
n
2
)
\theta(2^{\frac{n}{2}})
θ(22n?)
对于指数时间而言，其增长是灾难式的。这也是为什么动态规划能有如次神奇的魔力与广阔的应用空间。
? 要进行动态规划分析，最好的方法之一就是建立递归树模型，如下图所示：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JE6geTCs-1627120273918)(F:\Sixpence Project\DP-PY\斐波那契递归树.png)]
? 从上图中我们不难发现，在第三层中fib(n-3)被重复计算了两次，在后续的分支中，类似的重复计算也一直在发生以至于大量的程序运行时间被浪费在了“重复造轮子”而不是真正有效的计算中。而动态规划的解决思路就是设置一个字典或列表，使已经计算过的节点值被存放在字典或列表中。在调用时首先读取字典和列表，若值存在则直接返回；否则则进行递归计算并把得到的值存放在字典中。下面的代码给出了一种基于字典的斐波那契数列递归算法。
def FibonacciDP(i, memo):
if (i == 1) | (i == 2):
return 1
if ((i - 1) in memo) & ((i - 2) in memo):
return memo[i - 1] + memo[i - 2]
else:
memo[i - 1] = FibonacciDP(i - 1, memo)
memo[i - 2] = FibonacciDP(i - 2, memo)
return memo[i - 1] + memo[i - 2]
? 特别地，如果在调用该函数前，我们已经获得了斐波那契数列某些数的值与其对应的位数，我们可以将其传入初始调用的函数中。只要所求位置比至少一个传入列表的位置大，DP的运行时间将有可能进一步压缩。
? 同样的，我们还可以写出迭代版本的动态规划算法，迭代算法的理解难度远小于递归算法，但其要理解其核心，我们可以思考一个问题，即递归算法中的memo字典在此处变成了什么呢？下面给出计算斐波那契额数列的迭代算法：
def FibonacciDP2(i):
SUM1 = [1, 1]
if len(SUM1) >= i:
return SUM1[i - 1]
else:
for k in range(2, i):
SUM1.append(SUM1[k - 1] + SUM1[k - 2])
return SUM1[i - 1]
? 对基于DP的递归算法进行复杂度分析，我们可以知道其算法复杂度为：
θ
(
n
)
\theta(n)
θ(n)
通过记住我们已经完成的工作，算法速度有了质的提升（线性时间<<<多项式时间<<<指数时间），以至于在下面的例子中我们甚至无法进行有效的对比：
调用函数：Fibonacci(40)与FibonacciDP(40, {})
仅递归的运行时间： 33.00659251213074
递归+DP的运行时间： 0.0
3、动态规划的基本分析方法
? 动态规划虽然有着极大的魔力把指数时间替换为多项式时间，但对于不同的问题而言，其分析和建模往往是与问题本身的特点密切相关且环环相扣，较为复杂。但一般而言我们只需要进行下面五个步骤的操作，便可以设计出可行的动态规划算法，下面我将以在Fibonacci的例子对五步方法进行说明：
①对子问题进行定义
? Fib(n)的子问题有Fib(n-1)，Fib(n-2)，Fib(n-3)…
②猜猜子问题的数量与可能的排列方式
? 在Fibonacci数列中，子问题的数量为2，即每一个Fib(n)只由Fib(n-1)和Fib(n-2)所给出。
③所得到的子问题是否能继续用所猜测的方式继续求解
? 可以，因为n对所有2<k≤n, k为整数均成立。
④写出递归方程（状态转移方程）/ 建立DP表格模型
F
i
b
(
n
)
=
1
n
=
1
/
n
=
2
Fib(n)=1 \quad n=1 / n=2
Fib(n)=1n=1/n=2
F
i
b
(
n
)
=
F
i
b
(
n
?
1
)
+
F
i
b
(
n
?
2
)
2
<
n
≤
i
n
p
u
t
(
n
)
Fib(n) = Fib(n-1)+Fib(n -2)\quad 2<n\le input(n)
Fib(n)=Fib(n?1)+Fib(n?2)2<n≤input(n)
⑤写出代码，解决源问题
n=1 \or n=2
$$
F
i
b
(
n
)
=
F
i
b
(
n
?
1
)
+
F
i
b
(
n
?
2
)
2
<
n
≤
i
n
p
u
t
(
n
)
Fib(n) = Fib(n-1)+Fib(n -2)\quad 2<n\le input(n)
Fib(n)=Fib(n?1)+Fib(n?2)2<n≤input(n)
⑤写出代码，解决源问题
|