从零开始的Python ACM Ch.9：动态规划

1106 字

6 分钟

从零开始的Python ACM Ch.9：动态规划

2022-11-15

Coding

/

Dynamic

例题：跳台阶#

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1

输入：n = 2 输出：2

解释：有两种方法可以爬到楼顶。

1 阶 + 1 阶
2 阶

示例 2：

输入：n = 3 输出：3

解释：有三种方法可以爬到楼顶。

1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶

1 <= n <= 45

题解（递归法）#

解释：一个steps为n的问题可以看做是steps为n-1和steps为n-2的步骤和

1
steps = int(input('Steps: '))   # 台阶数
2

3
def degrade(steps):
4
    if steps == 1: return 1
5
    if steps == 2: return 2
6
    return degrade(steps - 1) + degrade(steps - 2)
7

8
print(degrade(steps))

这个方法可以发现，当输入steps为10时，degrade(9)计算了1次，degrade(8)计算了2次（degrade(9)里面一次，自身一次），再往下发现越往下计算的次数越多，如果计算式子很复杂会消耗更多的时间

所以有一个优化的方式，就是把已经算过的值丢到一个新的变量里面存起来，如果计算过就不用计算了（缓存优化）

1
steps = int(input('Steps: '))   # 台阶数
2
memory = [-1] * 10000000
3

4
def degrade(steps):
5
    if steps == 1: return 1
6
    if steps == 2: return 2
7
    if memory[steps] >= 0: return memory[steps]
8
    memory[steps] = degrade(steps - 1) + degrade(steps - 2)
9
    return memory[steps]
10

11
print(degrade(steps))

或者使用字典来存储

1
steps = int(input('Steps: '))   # 台阶数
2
memory = {}
3

4
def degrade(steps):
5
    if steps == 1: return 1
6
    if steps == 2: return 2
7
    if steps in memory: return memory[steps]
8
    memory[steps] = degrade(steps - 1) + degrade(steps - 2)
9
    return memory[steps]
10

11
print(degrade(steps))

递归问题#

步骤只有两步：

分解（分解为规模较小的相似问题）
原子问题（可以由问题分解推出，这里就是i=1和i=2的情况）

很多DP算法都能够用递归解决，因为这个比DP简单，所以先在这里列出来。

递归会占用系统资源，而且递归一定会比循环更慢一些（尽管你用了缓存优化），当递归数过高时会超过Python的最大深度，引起RecursionError然后就……像下面这样

1
Steps: 10000
2
Traceback (most recent call last):
3
  File "c:\Users\GamerNoTitle\.vscode\extensions\ms-python.python-2022.18.2\pythonFiles\lib\python\debugpy\_vendored\pydevd\_pydevd_bundle\pydevd_trace_dispatch_regular.py", line 359, in __call__
4
    is_stepping = pydev_step_cmd != -1
5
RecursionError: maximum recursion depth exceeded in comparison
6

7
During handling of the above exception, another exception occurred:
8

9
Traceback (most recent call last):
10
  File "C:\Users\GamerNoTitle\AppData\Local\Programs\Python\Python310\lib\runpy.py", line 196, in _run_module_as_main
11
    return _run_code(code, main_globals, None,
12
  File "C:\Users\GamerNoTitle\AppData\Local\Programs\Python\Python310\lib\runpy.py", line 86, in _run_code
13
    exec(code, run_globals)
14
  File "c:\Users\GamerNoTitle\.vscode\extensions\ms-python.python-2022.18.2\pythonFiles\lib\python\debugpy\__main__.py", line 39, in <module>
15
    cli.main()
16
  File "c:\Users\GamerNoTitle\.vscode\extensions\ms-python.python-2022.18.2\pythonFiles\lib\python\debugpy/..\debugpy\server\cli.py", line 430, in main
17
    run()
18
  File "c:\Users\GamerNoTitle\.vscode\extensions\ms-python.python-2022.18.2\pythonFiles\lib\python\debugpy/..\debugpy\server\cli.py", line 284, in run_file
19
    runpy.run_path(target, run_name="__main__")
20
  File "c:\Users\GamerNoTitle\.vscode\extensions\ms-python.python-2022.18.2\pythonFiles\lib\python\debugpy\_vendored\pydevd\_pydevd_bundle\pydevd_runpy.py", line 321, in run_path
21
    return _run_module_code(code, init_globals, run_name,
22
  File "c:\Users\GamerNoTitle\.vscode\extensions\ms-python.python-2022.18.2\pythonFiles\lib\python\debugpy\_vendored\pydevd\_pydevd_bundle\pydevd_runpy.py", line 135, in _run_module_code
23
    _run_code(code, mod_globals, init_globals,
24
  File "c:\Users\GamerNoTitle\.vscode\extensions\ms-python.python-2022.18.2\pythonFiles\lib\python\debugpy\_vendored\pydevd\_pydevd_bundle\pydevd_runpy.py", line 124, in _run_code
25
    exec(code, run_globals)
26
  File "c:\Users\GamerNoTitle\Desktop\Untitled.py", line 11, in <module>
27
    print(degrade(steps))
28
  File "c:\Users\GamerNoTitle\Desktop\Untitled.py", line 8, in degrade
29
    memory[steps] = degrade(steps - 1) + degrade(steps - 2)
30
  File "c:\Users\GamerNoTitle\Desktop\Untitled.py", line 8, in degrade
31
    memory[steps] = degrade(steps - 1) + degrade(steps - 2)
32
  File "c:\Users\GamerNoTitle\Desktop\Untitled.py", line 8, in degrade
33
    memory[steps] = degrade(steps - 1) + degrade(steps - 2)
34
  [Previous line repeated 983 more times]
35
  File "c:\Users\GamerNoTitle\Desktop\Untitled.py", line 4, in degrade
36
    def degrade(steps):
37
  File "c:\Users\GamerNoTitle\.vscode\extensions\ms-python.python-2022.18.2\pythonFiles\lib\python\debugpy\_vendored\pydevd\_pydevd_bundle\pydevd_trace_dispatch_regular.py", line 469, in __call__
38
    return None if event == 'call' else NO_FTRACE
39
RecursionError: maximum recursion depth exceeded in comparison

DP算法#

核心问题#

合成问题
初始状态（就是i=1和i=2的状态）
计算后续状态

DP算法求解#

还是上面那个跳台阶问题

1
steps = int(input('Steps: '))   # 台阶数
2

3
def degrade(steps):
4
    result = [0] * (steps + 1)
5
    result[1], result[2] = 1, 2
6
    for i in range(3, steps+1):
7
        result[i] = result[i-1] + result[i-2]
8
    return result[steps]
9

10
print(degrade(steps))

输出

1
Steps: 10000
2
54438373113565281338734260993750380135389184554695967026247715841208582865622349017083051547938960541173822675978026317384359584751116241439174702642959169925586334117906063048089793531476108466259072759367899150677960088306597966641965824937721800381441158841042480997984696487375337180028163763317781927941101369262750979509800713596718023814710669912644214775254478587674568963808002962265133111359929762726679441400101575800043510777465935805362502461707918059226414679005690752321895868142367849593880756423483754386342639635970733756260098962462668746112041739819404875062443709868654315626847186195620146126642232711815040367018825205314845875817193533529827837800351902529239517836689467661917953884712441028463935449484614450778762529520961887597272889220768537396475869543159172434537193611263743926337313005896167248051737986306368115003088396749587102619524631352447499505204198305187168321623283859794627245919771454628218399695789223798912199431775469705216131081096559950638297261253848242007897109054754028438149611930465061866170122983288964352733750792786069444761853525144421077928045979904561298129423809156055033032338919609162236698759922782923191896688017718575555520994653320128446502371153715141749290913104897203455577507196645425232862022019506091483585223882711016708433051169942115775151255510251655931888164048344129557038825477521111577395780115868397072602565614824956460538700280331311861485399805397031555727529693399586079850381581446276433858828529535803424850845426446471681531001533180479567436396815653326152509571127480411928196022148849148284389124178520174507305538928717857923509417743383331506898239354421988805429332440371194867215543576548565499134519271098919802665184564927827827212957649240235507595558205647569365394873317659000206373126570643509709482649710038733517477713403319028105575667931789470024118803094604034362953471997461392274791549730356412633074230824051999996101549784667340458326852960388301120765629245998136251652347093963049734046445106365304163630823669242257761468288461791843224793434406079917883360676846711185597501

DP与递归的区别#

DP是正着算，递归是反着算，仅此而已，思考问题的思路不同。

例题：网络路径数#

一个机器人位于一个 m x n 网格的左上角。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。

问总共有多少条不同的路径？

示例 1

输入：m = 3, n = 7 输出：28

示例 2

输入：m =3, n = 2 输出：3 解释：从左上角开始，总共有 3 条路径可以到达右下角。

向右 -> 向下 -> 向下
向下 -> 向下 -> 向右
向下 -> 向右 -> 向下

示例 3

输入：m =7, n = 3

输出：28

示例 4

输入：m = 3, n = 3

输出：6

题解（递归法）#

1
def pathcount(m, n):
2
    if m == 1 or n == 1: return 1
3
    return pathcount(m-1, n) + pathcount(m, n-1)

题解（DP法）#

1
def pathcount(m, n):
2
    ls = [[0 for _ in range(n+1)] for __ in range(m+1)]
3
    ls[1][1] = 0
4
    for i in range(1, len(ls[1])): # 初始化状态初值
5
        ls[1][i] = 1
6
    for i in range(1, len(ls)):
7
        ls[i][1] = 1
8
    ls[1][2] = 1
9
    ls[2][1] = 1
10
    for b in range(2, m+1): # b是行
11
        for a in range(2, n+1): # a是列
12
            ls[b][a] = ls[b-1][a] + ls[b][a-1]
13
    print(ls)
14
    return ls[m][n]