动态规划(dynamic planning)是一种高效解决问题的方法，适用于具有重复子问题和最优子结构的问题。

  • 如果可以把局部子问题的解结合起来得到全局最优解，那这个问题就具备最优子结构

  • 如果计算最优解时需要处理很多相同的问题，那么这个问题就具备重复子问题

当最优化问题具有重复子问题和最优子结构的时候，就是动态规划出场的时候了。动态规划算法的核心就是提供了一个memory来缓存重复子问题的结果，避免了递归的过程中的大量的重复计算。动态规划算法的难点在于怎么将问题转化为能够利用动态规划算法来解决。当重复子问题的数目比较小时，动态规划的效果也会很差。如果问题存在大量的重复子问题的话，那么动态规划对于效率的提高是非常恐怖的。

当要应用动态规划来解决问题时，归根结底就是想办法完成以下三个关键目标。

  1. 建立状态转移方程

这一步通常是最难的…，状态之间的关系。例如斐波那契数列，状态转移方程为：f(n)=f(n-1)+f(n-2)

  1. 缓存把那个复用以往结果

  2. 按顺序从小往大算

示例：

看看最简单的斐波那契数列：0,1,1,2,3 …… 从第0项开始，f(n) = f(n-1)+f(n-2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 传统的递归方式
def fibo(n):
    if n <= 1:
        return n
    return fibo(n - 1) + fibo(n - 2)

# 动态规划形式#1
def fibo_dp_1(n):
    memory = [0, 1]
    if n < 2:
        return memory[n]
    for i in range(2, n + 1):
        memory.append(memory[i - 1] + memory[i - 2])
    return memory[n]

# 动态规划#2递归形式
memory = [0,1]
def fibo_dp_2(n):
    if n <= 1:
        return memory[n]
    if n >= len(memory):
        memory.append(fibo_dp_2(n - 1) + fibo_dp_2(n - 2))
    return memory[n]

当计算的数较小时：三种方式花费时间差距并不大：

1
2
3
4
n = 10, res = 55
1: time cost:0.000063sec
2: time cost:0.000011sec
3: time cost:0.000014sec

当计算的数较大时，耗时差距就体现出来，动态规划缓存的重要性便凸显出来

1
2
3
4
n = 37, res = 24157817
1: time cost:16.511701sec
2: time cost:0.000026sec
3: time cost:0.000044sec

动态规划速度的快，是因为它将之前的小问题的结果保存在缓存中，而传统的递归方式，相当于重复计算小问题，因此耗时。

image-20200331161524036

当然这只是动态规划的最简单形式，动态规划的Leetcode专栏：

leetcode/动态规划

唉….我太菜了，很多时候找不到状态转移关系…