来谈谈动态规划

共计 2654 个字符，预计需要花费 7 分钟才能阅读完成。

在 leetcode 上做题时，经常会碰到有关动态规划的问题，在 leetcode 的题库界面可以看到有着动态规划标签的题目还是挺多的，为了搞明白这个东东，我查了不少资料，现在来整理一下思路，试试把动态规划这个概念讲清楚。

动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题 [1] 和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
——来自维基百科

这里的定义好像术语有点过多，我觉得最重要的就是那句“把原问题分解为相对简单的子问题的方式求解复杂问题 ”。动态规划将一个复杂的大问题分解成小问题， 拆解问题，就是动态规划的核心。

来看一道经典题目：

假设你正在爬楼梯，楼梯有 n 级台阶，你每次只能一级或两级楼梯，请问你一共有多少种方式爬完？
现在我们来试着解决这个问题：

先假设我们只爬五级楼梯，如果直接暴力枚举似乎有点麻烦，我们可以想一下，在你将要爬完的时候，也就是在爬到第五级之前，其实只有 两种情况 ，一种在第三级，一种在第四级。我们最终的解是爬完五级的全部走法，记为f(5)，那么假设爬三层总走法是f(3)，四层总数是f(4)，思考一下，爬完五层的走法总数是不是f(5)=f(3)+f(4) 呢？从第三级到第五级，爬两级，从第四到第五，爬一级。那么爬三级的走法加上爬四级的走法，刚好就是爬五级的走法总数。
这样推算下来，只要我们有爬一级和爬两级的情况，就可以用递归求 f(n)=f(n-1)+f(n-2) 了。爬一级就走一步，一种走法，爬两级，要么走两次一步，要么直接两级台阶一步到位，两种走法。
代码实现：

def climbStairs(n):
    if n < 1:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2
    return climbStairs(n-1) + climbStairs(n-2)

看上去没什么问题，让我们来看一下时间复杂度。

从这个图里可以看到直接使用递归是有 重复计算 的，并且当 n 越大，也就是楼梯级数越多，重复计算的量就越大，这是我们不可忍受的。
时间复杂度：O(2ⁿ)
空间复杂度：O(n)

既然有重复计算，那么我们把已经计算过的值用哈希表缓存起来，不就能提高效率了吗？
代码实现：

memo = {}
def climbStairs(n):
    if n in memo:
        return memo[n]
    if n < 1:
        return 0
    if n == 1 or n == 2:
        return n
    else:
        memo[n] = climbStairs(n-1) + climbStairs(n-2)
        return memo[n]

所有计算过的值都存储在 memo 这个字典里，如果结果已经在字典中，我们就不需要再重复计算了。
与前一个方法时间对比，把两个函数名改一下，使用 time.time() 方法来算一下执行时间：

if __name__ == '__main__':
    start = time.time()
    print(climbStairs1(35))
    print("递归耗时{:.8f} second".format(time.time()-start))
    start = time.time()
    memo = {}
    print(climbStairs2(35))
    print("备忘录耗时{:.8f} second".format(time.time()-start))
    
# 结果
14930352
递归耗时 6.11950040 second
14930352
备忘录耗时 0.00399756 second
>>>

可以看到速度有很明显的提示。
时间复杂度：O(n)
空间复杂度：O(n)

在前面两个方法中，我们都是从 n 级台阶往下推导，那么可不可以直接利用f(1) 和f(2)向上迭代呢？
代码实现：

def climbStairs(n):
    if n < 1:
        return 0
    if n == 1 or n == 2:
        return n
    first, second = 1, 2
    for i in range(n-2):
        first, second = second, first+second

显然这个算法时间复杂度为 O(n)，由于只引入了两个变量，空间复杂度相比前两种方法降到了 O(1)。
时间复杂度：O(n)
空间复杂度：O(1)
其实，关于这个问题还有 时间复杂度：O(log(n))，空间复杂度：O(1)的解法，详见 https://leetcode-cn.com/probl…

定义状态：

计算机在本质上是状态机，内存中的数据构成当前状态，CPU 根据当前状态计算出下一状态。
在我们的爬楼梯问题中，当前的 f(n)是一个状态，我们确定了它由 f(n-1)和 f(n-2)构成，f(n-1)和 f(n-2)又是两种状态。
2. 状态转移方程
状态定义好后，列出状态与状态之间的关系式，就叫状态转移方程。
f(n)=f(n-1)+f(n-2)
f(1) = 1 #边界情况
f(2) = 2 #边界情况
根据状态定义可以推导出边界情况，当状态为边界情况时我们直接得到结果。我发现网上很多文章里都会讲到很多 最优子结构 、 无后效性 、 重叠子问题 等概念，这些东西都可以搜索到，就不赘述了。
事实上要用好动态规划，我觉得要点是要分析好问题，对问题进行适当的建模。有的文章说动态规划是以空间换时间，记忆推导，个人认为这并不算动态规划的本质。

纸上得来终觉浅，绝知此事要躬行
说了这么多，要想真正理解还是需要实际去操作一番，去 leetcode 找一些动态规划相关的题目做一做。记住，最少要思考一到两个小时没有想出办法才去看别人的解法，否则和没有做题是没区别的。

https://www.zhihu.com/questio…
https://leetcode-cn.com/probl…
https://blog.csdn.net/u013309…
https://juejin.im/post/5a29d5…

扫描二维码关注公众号：

前言

引用段维基

来举个栗子

1. 递归解决

2. 自顶向下备忘录

3. 自底向上动态规划

分析问题

快去练练手

参考了哪些

Just My Socks（注册教程内含优惠码）