一、什么是动态规划？

动态规划（Dynamic Programming）是一个非常经典的算法，它的核心思想很简单：

把一个大问题拆解成已知解的子问题。

怎么说呢？举一个简单的例子吧：

斐波那契数列: 1, 1, 2, 3, 5, 7, 12, 19, 31 ...

即：第一个数和第二个数都是1，接下来的每一个数都是前两个数的和。

也即：

<code>f(1) = f(2) = 1
f(n) = f(n-1) + f(n-2)/<code>

例如：

<code>f(1) = 1

f(2) = 1

f(3) = f(1) + f(2) = 1+ 1 = 2

f(4) = f(3) + f(2) = 2 + 1 = 3

...

f(n) = f(n-1) + f(n-2)/<code>

假设我们想要求f(4)的值，如果我们已经之前已经计算过f(3)和f(2)就可以直接给出f(4) = f(3) + f(2) = 2 + 1 = 3，而不需要从f(1) = f(2) = 1来一步步推算到第四个数了。

有这样一句话非常生动的说明了动态规划的核心：

不能记住历史，就注定会重复历史。

二、爬楼梯问题

再来看看经典的爬楼梯问题：

<code>有一个楼梯，一共有n个台阶。
每次你可以上一个或者两个台阶，那么爬到楼梯顶有多少中不同的爬法呢？

注意：n是一个正整数 


例子一：
输入：2个台阶
输出：2种爬法
解释：两种爬法分别为：
1. 爬一个台阶 + 爬一个台阶
2. 爬两个台阶

例子二：
输入：3个台阶
输出：3种爬法
解释：三种爬法分别为：
1. 爬一个台阶 + 爬一个台阶 + 爬一个台阶
2. 爬一个台阶 + 爬两个台阶
3. 爬两个台阶 + 爬一个台阶/<code>

大家先思考一下怎么解决这个问题？

好了，有想法了吗？如果没有思路的话，联想一下一开始说的动态规划：把一个大问题拆解成已知解的子问题。

这里要反直觉地假设一下，如果我现在已经站在楼梯顶（第n个台阶），那我是怎么上来的呢？

由于我只能一次跨一个或者两个台阶，所以我上一步必然在第n-1个台阶或者第n-2个台阶上，那么我爬到楼梯顶的爬法就是爬到第n-1个台阶的爬法+爬到第n-2个台阶的爬法之和，也就是：

<code>f(n) = f(n-1) + f(n-2)/<code>

且一阶台阶的爬法只有1种，二阶台阶的爬法只有2种（1+1或者2），即：

<code>f(1) = 1
f(2) = 2/<code>

用python代码实现就是：

<code>class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        elif n == 2:
            return 2
        return self.climbStairs(n-1) + self.climbStairs(n-2)/<code>

是不是很简单？！

是的，以上就是爬梯子问题使用了递归（Recursion）方法的暴力解法（Brute Force）。在不考虑时间复杂度和空间复杂度的情况下，能够解决问题。

三、给递归加上记忆(Memoization)

上面的那个解法就是最基本的递归解法。

<code>递归：一个函数在内部调用自身/<code>

基本的递归解法确实能够解决问题，但是递归解法的问题也十分明显：在n数值大的时候，时间复杂度和空间复杂度非常之大（分别为O(2^n)和O(n)），对于较大的n，甚至无法在给定时间内解出。让我们看看当n等于5时的递归调用树：

<code>f(5)  
  =  f(4) + f(3) 
  = f(3) + f(2) + f(2) + f(1)
  = f(2) + f(1) + f(2) + f(2) + f(2) + f(1)/<code>

f函数的计算次数实在是太多。

那如何改进呢？

其实很简单，我们都可以看到对于相同的值，并不需要计算多次，比如说上图中对于f(1) , f(2), f(3)的结果，只需要在第一次计算后保存下来，下一次需要的时候直接查询就可以大大减少计算量。

用python代码实现就是：

<code>class Solution:
    res = {}
    
    def climbStairs(self, n: int) -> int:
        if n == 1:
            self.res[1] = 1
            return 1
        elif n == 2:
            self.res[2] = 2
            return 2
        res_val = self.res.get(n) or self.climbStairs(n-1) + self.climbStairs(n-2)
        self.res[n] = res_val
        return res_val/<code>

以上解法的时间复杂度和空间复杂度可以降低到：O(n) 和 O(n)

四、动态规划

上面的递归解法的思路是自顶向下，先算f(5), 再算f(4), f(3), 再算f(2), f(1)。

那我们能不能利用动态规划的思路，先算小问题，最后算出大问题，自底向上地算出最终解呢？

当然可以：

<code>已知:
f(1) = 1, f(2) = 2
可知:
f(3) = f(2) + f(1) = 2 + 1 = 3
f(4) = f(3) + f(2) = 3 + 2 = 5
.../<code>

用python代码实现就是：

<code>class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        elif n == 2:
            return 2
        res_n_1 = 2
        res_n_2 = 1
        res_n = None
        for i in range(n-2):
            res_n = res_n_1 + res_n_2
            res_n_2 = res_n_1
            res_n_1 = res_n
        return res_n/<code>

时间复杂度和空间复杂度分别为：O(n) 和 O(n)

五、后续

到这里，有没有觉得动态规划其实很简单呢？

只要掌握了正确了学习方法，加上持之以恒的学习训练，算法并不难~

上面的爬楼梯问题其实还有性能更优化的方案，你能想到吗？

我是零度橙子，5年以上python经验，软件工程师，科技达人，谷歌认证云计算架构师，AWS认证devops专家，欢迎大家关注我，了解有用有趣的科技知识~

閱讀更多 零度橙子 的文章

關鍵字: Python 数列 斐波