Day 11 - Pre-Knowledge for Dynamic Programming
Day11 - 动态规划前置知识
1. 动态规划介绍
动态规划（Dynamic Programming）常用于解决具有重叠子问题和最优子结构的问题。动态规划基于递归的思想，将问题分解成更小的子问题，并利用子问题的解来求解原问题，求解原问题的过程中通过存储子问题的解来避免重复计算，从而提高效率。
通常只需要三步就可以解决所有的动态规划问题。
实现原问题的递归解法。
采用备忘录(数组或哈希表)对递归解法进行优化。
将优化后的算法采用自下而上的迭代重新实现。
下面我们通过著名的斐波那契数列问题来看一下整个过程。
斐波那契数列是一个经典的数学序列，以意大利数学家斐波那契的名字命名。该数列从0和1开始，之后的每一项都是前两项的和。
2. Fiber 数列的递归解法
观察斐波那契数列的规律，我们可以得到其递推形式：
fib(0) = 0, fib(1) = 1, fib(2) = 1
fib(n) = fib(n-1) + fib(n-2)（n > 2）当前问题的最优子结构就体现在上面的递推公式中，当前问题的解可以通过子问题的解来构造，即 fib(n) 可以通过 fib(n-1) 和 fib(n-2) 来计算得到。
纯粹的递归解法如下：
def fib(n):
if n <= 1:
return n
else:
return fib(n-1) + fib(n-2)下图是fib(5)对应的递归树。
从上面的递归树中我们可以看出，fib(3) , fib(2), fib(1)会被计算多次，从而对于较大的 n 值，会存在大量的重复计算，效率较低，这就是一开始提到的重叠子问题。其时间复杂度为O(2^n)，这是一个指数级的时间复杂度，对于一段代码，这种复杂度简直就是一场灾难。递归涉及到栈的使用，其空间复杂度为O(n)。
3. 利用备忘录对递归进行优化
备忘录法是一种通过保存已经计算过的结果来避免重复计算的方法。由于上面的递归解法中存在大量的重复计算，我们可以利用一个数据结构（通常是数组或哈希表）来存储已经计算过的结果，当需要再次计算时，首先检查备忘录中是否已经有了结果，如果有，则直接返回该结果，否则进行计算。
下面给出了增加备忘录以后的递归代码。
memo = {}
def fib(n):
if n in memo:
return memo[n]
if n <= 1:
return n
else:
memo[n] = fib(n-1) + fib(n-2)
return memo[n]虽然递归看起来是自上而下的层层分解，这里的备忘录实际上是一个隐式的自下而上填表的过程，避免了重复计算，增加备忘录以后的递归解法的时间复杂度为O(n)，大大提高了计算的效率，但需要额外的空间来存储备忘录，这也是常说的用空间换时间。这里的空间复杂度依旧是O(n)。
既然带备忘录的递归解法，其本质是隐式的自下而上填表，那我们何不直接通过迭代的方式自下而上的构建问题的解呢？
因此自下而上的迭代实现就应运而生。
4. 使用自下而上的迭代重新实现
自下而上是动态规划的另一种实现方式，与递归相反，它从最小的子问题开始逐步构建解，直到解决原问题，这种方法通常采用迭代实现。
下面是自下而上迭代的代码实现。
def fib(n):
if n <= 1:
return n
dp = [0] * (n+1)
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]分析上面的代码实现，因为数列当前的值只依赖其前面两个数列的值，我们可以进一步优化空间的使用，优化后的代码如下。
def fib(n):
if n <= 1:
return n
pre, cur = 0, 1
for _ in range(2, n+1):
pre, cur = cur, pre + cur
return cur所以自下而上的迭代甚至可以不需要额外的空间来存储备忘录，更加节省空间，这里的空间复杂度为O(1)。
自下而上的迭代关键在于确定子问题的求解顺序，以确保每个子问题的解都已经计算过。通过自下而上的顺序求解子问题，可以保证每个子问题的解都是基于之前已经求解的子问题，从而确保整体问题的解的正确性，整体的时间复杂度是O(n)。
5. 总结
动态规划是一种重要的问题求解方法，自上而下带备忘录的递归和自下而上的迭代都是动态规划实现方式。
下面是在一维动态规划问题中两种实现方式的时空复杂度对比：
实现方法
时间复杂度
空间复杂度
带备忘录的递归
O(n)
O(n)
迭代
O(n)
能做到O(1)
带备忘录的递归实现可以帮我们更好的理解动态规划，但是有些编程语言，比如python对递归的层级是有限制的，自下而上的迭代相比带备忘录的递归，省去了递归过程中栈的使用，甚至还可以省去备忘录的使用，是实现动态规划问题的最佳选择。
对于所有的动态规划问题，都可以采用上面的步骤，一步一步去实现它的迭代解法。
Last updated