动态规划是一种求最优解的方式，个人了解也不是很深，胡乱写写，算是一点点自己的理解，有不对的地方欢迎批评。动态规划是一种在多个状态间进行转移时，由上一个最优状态推导出下一个最优状态的方式，而上一个最优状态又是由上上个最优状态推导得到的，如此不断向前推进，最后我们只需要知道初始最优状态即可。通过初始最优状态和状态间转移的逻辑和方式，我们就能获得全局最优状态。（是不是感觉有点像数学归纳法？）

举一个斐波拉契数列的例子，最简单的解法自然是使用递归实现

1
2
3
4
5
6
def fab(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fab(n - 1) + fab(n - 2)

简单分析就可以发现，以上例子中，很多的数字被重复计算了。例如在计算fab(5)时fab(3)已经被计算了，但是在计算fab(4)时fab(3)又被计算了一遍。因此，我们可以用一个table保存已经计算好的数据，避免重复计算

1
2
3
4
5
6
7
8
9
10
11
12
table = {}
def fab(n):
    if n in table:
        return table[n]
    if n == 0:
        result = 0
    elif n == 1:
        result = 1
    else:
        result = fab(n - 1) + fab(n - 2)
    table[n] = result
    return result

更改了策略之后，我们发现计算速度快了很多，这其实就是动态规划需要避免的重叠子问题，这些重叠子问题的存在导致如果使用暴力穷举会产生很多额外的计算量。动态规划的解决办法就是找到最优子结构，通过不断的在最优子结构之间进行状态转移，最终得到最优解，而这个状态转移逻辑就称为状态转移方程。

再次观察可以知道，其实斐波拉契数列的计算只依赖于当前的值的前两个值，所以我们并不需要使用一个table来存数据，而只需要存储两个前值变量即可

1
2
3
4
5
6
7
8
9
10
11
12
def fab(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    a = 0
    b = 1
    for i in range(2, n + 1):
        tmp = a + b
        a = b
        b = tmp
    return b

从上面我们就可以知道，其实斐波拉契数列的计算过程就是一个使用最优子结构和状态转移方程还有初始状态，最终获得全局最优解的过程。下面再看一个跳台阶的例子

有一个楼梯，一次可以跳1个台阶或者2个台阶，问跳n个台阶一共有多少种跳法

上面的问题看似无从着手，但是如果使用上面的动态规划思想思索一下就可以想到，跳n个台阶的跳法，其实就等于跳n - 1个台阶的跳法数目，加上跳n - 2个台阶的跳法数目。为什么可以这样考虑呢，因为跳到最后一个台阶，可能是从第n - 1个台阶跳了一个台阶跳上去的，所以这种情况下只需要考虑n - 1个台阶有多少种跳法即可。当然还有一种可能，是从第n - 2个台阶跳了两个台阶跳上去的，此时只需要考虑n - 2个台阶的跳法数量即可。因此，跳n个台阶的跳法其实就等于n-1和n-2个台阶的跳法之和，即

DP[n] = DP[n - 1] + DP[n - 2]

转移方程确定之后，我们只需要再确定初始状态即可（是不是越发的感觉像数学归纳法了）。简单分析就可以发现，跳1个台阶有1种跳法，跳2个台阶有2种跳法（一次跳2个，或者一次跳1个跳2次）。即

DP[1] = 1
DP[2] = 2

因此我们可以构建如下代码逻辑

1
2
3
4
5
6
7
8
9
10
11
12
def jump(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    a = 1
    b = 2
    for i in range(3, n + 1):
        tmp = a + b
        a = b
        b = tmp
    return b

如上就是一个典型的动态规划解决问题的过程。我们再看一个问题

给k种面值的硬币，面值分别为c1, c2 … ck，每种硬币的数量无限，再给一个总金额amount，问最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回-1

有了上面的训练，这题我们就可以稍微有点思路了。首先我们需要确定状态转移方程，这里的状态就是总金额，而状态转移就是金额跟随着硬币的增加而产生的剩余金额变化。要知道amount的最小硬币数，其实我们只需要知道amount - c的最小硬币数，amount的最小硬币数就是amount - c的最小硬币数再加1。但是因为有多个硬币，所以我们还需要对不同的amount - c进行判断，先得到其前置条件的最优解。

我们可以得到其状态转移方程

DP[n] = min(DP[n - c1], DP[n - c2] ... DP[n - ck]) + 1

其中DP[0] = 0，DP[负数] = -1。由此我们可以构建如下代码逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def coin_problem(coins, amount):
    coin_problem_table = dict()  # {"金额":"硬币数"}
    def dp(n):
        if n in coin_problem_table:
            return coin_problem_table[n]
        if n == 0:
            return 0
        if n < 0:
            return -1
        res = None
        for coin in coins:
            val = dp(n - coin)  # 分解为子问题
            if val == -1:
                continue  # 没有解，就尝试下一个硬币
            if res is None or res > val:
                res = val  # 最优子解
        if res is None:  # 没有解
            res = -1
        else:
            res += 1  # 加上这次新加的硬币
        coin_problem_table[n] = res
        return res
    return dp(amount)

以上问题其实是LeetCode的一个零钱兑换问题，如上代码在LeetCode中超过了93%的提交，效率还是不错的。

上面我们说的都是一维的问题，事实上动态规划时常会以二维数组的形式出现，下面我看一个例子

一个机器人位于一个 m x n 的网格左上角，机器人每次只能向右或向下走一格，问机器人走到右下角有多少种方式？

看到了问题，我们就可以开始分析，机器人走到右下角的路径，肯定可以由它到右下角之前的前一个格子的路径推导得到。假设我们把格子都标上坐标，横着的用i表示，竖着的用j表示，显然0 <= i <= m - 1且0 <= j <= n - 1，我们也可以得到DP转移方程

DP[i][j] = DP[i - 1][j] + DP[i][j - 1]

此外，我们可以发现，在最左边一列或者最上面一行的所有方格，其都只有一种走法。即对于最左一列，机器人只能往下走，对于最上面一行，机器人只能往右走，由此我们可以得到初始状态

DP[0...m - 1][0] = 1
DP[0][0...n - 1] = 1

得到了转移方程和初始状态，那么实现代码也就很简单了

1
2
3
4
5
6
7
8
9
10
def robot_maze(m, n):
    dp = [[0] * n] * m  # 创建二维数组
    for i in range(m):  # 第一行
        dp[i][0] = 1
    for j in range(n):  # 第一列
        dp[0][j] = 1
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[m - 1][n - 1]

这同样也是LeetCode的一道题目，我的实现超过了91%的时间和60%的内存，效率也还是不错的。

上面我们介绍了动态规划的思路和解决问题的方式，其中最重要的就是状态转移和初始状态的确定。通过这些练习，我们对动态规划已经有了一些了解，看起来我们已经熟悉了动态规划了。但事实是动态规划难就难在其变种太多，并且有些问题的状态转移很抽象。遇到这些变种的时候，我们可能很难才能确定状态设计和状态转移方程，这些只能通过不断地去练习刷题才能有所提升。

本文涉及到的完整代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
import time


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


table = {}


def fab2(n):
    if n in table:
        return table[n]

    if n == 0:
        result = 0
    elif n == 1:
        result = 1
    else:
        result = fab2(n - 1) + fab2(n - 2)
    table[n] = result
    return result


def fab3(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    a = 0
    b = 1
    for i in range(2, n + 1):
        tmp = a + b
        a = b
        b = tmp
    return b


def jump(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    a = 1
    b = 2
    for i in range(3, n + 1):
        tmp = a + b
        a = b
        b = tmp
    return b


def coin_problem(coins, amount):
    coin_problem_table = dict()  # {"金额":"硬币数"}

    def dp(n):
        if n in coin_problem_table:
            return coin_problem_table[n]

        if n == 0:
            return 0
        if n < 0:
            return -1

        res = None
        for coin in coins:
            val = dp(n - coin)  # 分解为子问题
            if val == -1:
                continue  # 没有解，就尝试下一个硬币
            if res is None or res > val:
                res = val  # 最优子解

        if res is None:  # 没有解
            res = -1
        else:
            res += 1  # 加上这次新加的硬币

        coin_problem_table[n] = res
        return res

    return dp(amount)


def robot_maze(m, n):
    dp = [[0] * n] * m  # 创建二维数组

    for i in range(m):  # 第一行
        dp[i][0] = 1
    for j in range(n):  # 第一列
        dp[0][j] = 1

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    return dp[m - 1][n - 1]


if __name__ == '__main__':
    # x = 35
    #
    # start = time.time()
    # print(fab1(x))
    # print('fab1 cost: {}ms'.format((time.time() - start) * 1000))
    #
    # start = time.time()
    # print(fab2(x))
    # print('fab2 cost: {}ms'.format((time.time() - start) * 1000))
    #
    # start = time.time()
    # print(fab3(x))
    # print('fab3 cost: {}ms'.format((time.time() - start) * 1000))

    # print(jump(7))

    # print(coin_problem([186, 419, 83, 408], 6249))

    print(robot_maze(3, 7))

参考

如何学好动态规划
什么是动态规划（Dynamic Programming）？动态规划的意义是什么？ - 帅地的回答 - 知乎