算法 - 动态规划基础

2020-08-05 10:11:32

动态规划是数据结构和算法中比较难的一部分，我学动态规划也是走走停停，从来没有完整学完过动态规划。所以我打算这一次完完整整的学完动态规划，并通过写题解的方式记录下来。

接下来是正文。

动态规划是什么？又是一个非常高大上的一个名词，百度百科解释如下：

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

解释很专业，但是我是没太明白说的是个啥

学动态规划讲的比较详细的是《算法导论》，建议参看。

动态规划简单讲就是一个利用空间换取时间降低时间复杂度的一个技术。

讲动态规划一定离不开斐波那契数列问题。斐波那契数列的关系式： $f(n) = f(n - 1) + fib(n - 2), f(n) = 1, n < 2$

这样的一个关系式在动态规划叫做状态转移方程，就是状态n有n-1和n-2转移过来的。首先写一个暴力解时间复杂度$O(2^n)$

1
2
3
def fib(n):
    if n < 2: return 1
    return fib(n - 1) + fib(n - 2)
1
2
for i in range(10):
    print(fib(i), end=" ")
1 1 2 3 5 8 13 21 34 55

当n达到40左右的时候，程序就会非常慢了。有兴趣的可以试一下，因为这是指数级时间复杂度。

画下递归树以fib(8)为例：

在算fib(8)的时候，计算了1次fib(7), 2次fib(6), 3次fib(5)， 4次fib(4)。也就有一个现象，就是重复计算。

如何避免重复计算就可以把时间复杂度降低了，很直接的一个想法就是把每次计算的值存到一个地方，下次如果需要用的时候，在直接取出来，就可以避免重复计算了。就是很直白的一个空间换时间的一个想法，也就是动态规划(DP)。

这里我用哈希表来存放计算的数值，用数组或者其他的数据结构也行。

1
2
3
4
5
6
7
8
def fibMemo(n, memo={}):
    try:
        return memo[n]
    except KeyError:
        if n < 2: return 1
        res = fibMemo(n - 1) + fibMemo(n - 2)
        memo[n] = res
        return res
1
fibMemo(100)
573147844013817084101

这样可以很快的算出斐波那契数。因为哈希表每次的寻址时间复杂度是$O(1)$， 所以，整个算法的时间复杂度就是$O(n)$。

到这里，已经是动态规划了，它有个名字叫做自上而下版本，是递归的形式，但是往往需要改成非递归版本。因为非递归版本使用空间更小，递归版本容易发生爆栈。

至于怎么改非递归版本，这里有个小套路，如果写了递归版本，那么可以根据递归版本套路改，或者，直接递归方程式写。

1
2
3
4
5
6
7
8
9
10
11
def fibUnrecur(n):
    # 这里属于判特，n 不能小于0
    if n < 0: return 1
    # 这里用数组，dp也叫表格法
    dp = [0]*(n + 1)
    # n < 2， fib(n) = 1
    dp[0] = dp[1] = 1
    # 然后n >= 2，从2开始递推
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
1
fibUnrecur(100)
573147844013817084101

这里的dp[0], dp[1]属于递归的base case， 然后从2 ~ n进行递推，只是把递归的写法fib(n) = fib(n - 1) + fib(n - 2)变换成了，dp[i] = dp[i - 1] + dp[i - 2]。这个可以很直观的看出来时间复杂度是$O(n)$， 空间复杂度是$O(n)$。

到这里，其实基本上已经结束了，但是这道题还有个小小的空间优化，由状态转移方程可以看出，n的状态只和n - 1和n - 2有关系，这里就可以进行空间的优化。

1
2
3
4
5
def fibFinal(n):
    a, b = 1, 1
    for i in range(2, n + 1):
        a, b  = b, a + b
    return b
1
fibFinal(100)
573147844013817084101

这里的时间复杂度是$O(n)$的， 空间复杂度是$O(1)$。到这里就是动态规划的全部过程。

细心的你可能已经发现了，动态规划最难的部分不在于敲代码，在于写状态方程式。如果你能写出状态方程式，那么改动态规划还是比较套路化的。当然有些个别题例外，大部分都是考状态转移方程，至于怎么写出状态转移方程，套路就是，多刷题，多练，当然也有大佬总结出一些常见的动态规划的模板比如比较出名的是dd大牛的《背包九讲》，群里有上传文件。

总结一下：

  • 写出状态转移方程， 或者递归表达式。(两个东西是一样的，写出一个一定能写出另一个)
  • 改动态规划，如果能够优化空间复杂度就优化空间复杂度。

推荐几道练手题：

类似于斐波那契数列 - 三步问题
推dp表格 - 礼物的最大价值
01背包问题 - 打家劫舍
完全背包问题- 零钱兑换