小米 6 首席研究员的研究报告集

Hi there!

Python数据结构与算法补全系列(二)--递归和动态规划

Posted on Edited on In ,

递归

递归（Recursion）是解决问题的一种方法，它将问题不断地分成更小的子问题，直到问题可以用普通的方法解决。通常情况下，递归会使用一个不停调用自己的函数。

递归三原则

  • 递归算法必须有基本情况
  • 递归算法必须改变其状态并向基本情况靠近
  • 递归算法必须递归地调用自己

用递归解决汉诺塔问题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def move_tower(height, frompole, topole, withpole):
    if height >= 1:
        move_tower(height-1, frompole, withpole, topole)
        move_disk(frompole,topole)
        move_tower(height-1, withpole, topole, frompole)

def move_disk(fp, tp):
    print(f'moving disk from {fp} to {tp}')

>>> move_tower(3, 'frompole', 'topole', 'withpole')
moving disk from frompole to topole
moving disk from frompole to withpole
moving disk from topole to withpole
moving disk from frompole to topole
moving disk from withpole to frompole
moving disk from withpole to topole
moving disk from frompole to topole

动态规划

动态规划(Dynamic programming)是解决多阶段决策过程最优化的一种数学方法。把多阶段问题变换为一系列相互联系的的单阶段问题，然后逐个加以解决。

可用动态规划解决的问题的必要条件

  • 无后效性：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响（未来与过去无关）
  • 最优子结构：大问题的最优解可以由小问题的最优解推出

递归与动态规划解决找零问题的比较

1
2
3
4
5
6
7
8
9
10
11
12
13
# 找零问题的递归解决方案
def recmc(coinvaluelist, change):
    min_coins = change
    if change in coinvaluelist:
        return 1
    else:
        for i in [c for c in coinvaluelist if c <= change]:
            num_coins = 1 + recmc(coinvaluelist, change-i)
            if num_coins < min_coins:
                min_coins = num_coins
    return min_coins
>>> recmc([1, 5, 10, 25], 63)
6

上述代码的缺陷是效率奇低。针对找零金额是 63 分的情况，它需要进行 67716925 次递归调用才能找到最优解。
减少计算量的关键在于记住已有的结果。简单的做法是把最少硬币数的计算结果存储在一张表中，并在计算新的最少硬币数之前，检查结果是否已在表中。如果是，就直接使用结果，而不是重新计算:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 添加查询表之后的找零算法
def recdc(coinvaluelist, change, knownresults):
    mincoins = change
    if change in coinvaluelist:
        knownresults[change-1] = 1
        return 1
    elif knownresults[change-1] > 0:
        return knownresults[change-1]
    else:
        for i in [c for c in coinvaluelist if c <= change]:
            numcoins = 1 + recdc(coinvaluelist, change-i,
                                knownresults)
            if numcoins < mincoins:
                mincoins = numcoins
                knownresults[change-1] = mincoins
    return mincoins

>>> recdc([1, 5, 10, 25], 63, [0]*63)

修改后的算法将计算找零 63 分所需的递归调用数降低到 221 次。
上面打码所做的优化并不是动态规划，而是通过记忆化（或者叫作缓存）的方法来优化程序的性能。
真正的动态规划算法会用更系统化的方法来解决问题。在解决找零问题时，动态规划算法会从 1 分找零开始，然后系统地一直计算到所需的找零金额。这样做可以保证在每一步都已经知道任何小于当前值的找零金额所需的最少硬币数。 

1
2
3
4
5
6
7
8
def dp_make_change(coin_value_list, change, min_coins):
    for cents in range(change+1):
        coin_count = cents
        for j in [c for c in coinv_value_list if c <= cents]:
            if min_coins[cents-j] + 1 < coin_count:
                coin_count = min_coins[cents-j] + 1
        min_coins[cents] = coin_count
    return min_coins[change]

返回实际问题，上述代码虽然给出了最小硬币数但没有记录所需要的硬币。对上述代码进行如下优化：

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
# 修改后的动态规划解法
def dp_make_change(coin_value_list, change, min_coins, coins_used):
    for cents in range(change + 1):
        coin_count = cents
        new_coin = 1
        for j in [c for c in coin_value_list if c <= cents]:
            if min_coins[cents-j] + 1 < coin_count:
                coin_count = min_coins[cents - j] + 1
                new_coin = j
        min_coins[cents] = coin_count
        coins_used[cents] = new_coin
    return min_coins[change]

def print_coins(coin_used, change):
    coin = change
    while coin > 0:
        this_coin = coins_used[coin]
        print(this_coin)
        coin = coin - this_coin
>>> cl = [1, 5, 10, 21, 25]
>>> coinsUsed = [0]*64
>>> coinCount = [0]*64
>>> dpMakeChange(cl, 63, coinCount, coinsUsed) 
3
>>> printCoins(coinsUsed, 63)
21
21
21
>>> printCoins(coinsUsed, 52)
10
21
21
>>> coinsUsed
[1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 21, 1, 1, 1, 25, 1, 1, 1, 1, 5, 10, 1, 1, 1, 10, 1, 1, 1, 1, 5, 10, 21, 1, 1, 10, 21, 1, 1, 1, 25, 1, 10, 1, 1, 5, 10, 1, 1, 1, 10, 1, 10, 21]