递归与分治策略

[TOC]

分治策略

解决问题的典型策略： 分而治之，将问题分为若干更小规模的部分，通过解决每一个小规模部分问题，并将结果汇总，得到原问题的解

递归算法与分治策略

  • 递归三定律：
    • 基本结束条件，解决最小规模问题
    • 缩小规模，向基本结束条件演进
    • 调用自身来解决已缩小规模的相同问题
  • 体现了分治策略
    • 问题解决依赖于若干缩小了规模的问题
    • 汇总得到原问题的解
  • 应用相当广泛
    • 排序、查找、遍历、求值等等

找零兑换问题：递归解法

  • 其次是减小问题的规模， 我们要对每种硬币尝试 1次， 例如美元硬币体系：
  • 找零减去1分(penny)后，求兑换硬币最少数量（递归调用自身）；
  • 找零减去5分(nikel)后，求兑换硬币最少数量
  • 找零减去10分(dime)后，求兑换硬币最少数量
  • 找零减去25分(quarter)后，求兑换硬币最少数量
  • 上述4项中选择最小的一个。 
1
2
3
4
5
6
7
8
9
10
11
def recMC(coinValueList, change):
    minCoins = change
    if change in coinValueList:
        return 1
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recMC(coinValueList, change-i,knownResults)
            if numCoins < minCoins:
                minCoins = numCoins
     return minCoins
print(recMC([1,2,10,25],63))

递归解法虽然能解决问题， 但其最大的问题是： 极！ 其！ 低！ 效！
对63分的兑换硬币问题，需要进行67,716,925次递归调用！,就是重复计算太多！

找零兑换问题：递归解法改进

对这个递归解法进行改进的关键就在于消除重复计算我们可以用一个表将计算过的中间结果保存起来，在计算之前查表看看是否已经计算过

  • 这个算法的中间结果就是部分找零的最优解， 在递归调用过程中已经得到的最优解被记录下来
    • 在递归调用之前，先查找表中是否已有部分找零的最优解
    • 如果有， 直接返回最优解而不进行递归调用如果没有，才进行递归调用 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def recDC(coinValueList, change, knownResults):
    minCoins = change
    if change in coinValueList:
        knownResults[change] = 1  # 记录最优解
        return 1
    elif knownResults[change] > 0:
        return knownResults[change] # 查询结果中是否已经存在
    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] = minCoins
    return minCoins

中间结果记录可以很好解决找零兑换问题，实际上， 这种方法还不能称为动态规划，而是叫做“memoization（记忆化/函数值缓存） ”的技术提高了递归解法的性能

动态规划解法

  • 动态规划算法采用了一种更有条理的方式来得到问题的解

  • 找零兑换的动态规划算法从最简单的“1分钱找零”的最优解开始， 逐步递加上去， 直到我们需要的找零钱数

  • 在找零递加的过程中， 设法保持每一分钱的递加都是最优解， 一直加到求解找零钱数， 自然得到最优解

  • 递加的过程能保持最优解的关键是， 其依赖于更少钱数最优解的简单计算， 而更少钱数的最优解已经得到了。

  • 问题的最优解包含了更小规模子问题的最优解， 这是一个最优化问题能够用动态规划策略解决的必要条件 

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
def dpMakeChange(coinValueList,change,minCoins,coinsUsed):
   for cents in range(change+1):
      coinCount = cents
      newCoin = 1
      for j in [c for c in coinValueList if c <= cents]:
            if minCoins[cents-j] + 1 < coinCount:
               coinCount = minCoins[cents-j]+1
               newCoin = j
      minCoins[cents] = coinCount
      coinsUsed[cents] = newCoin
   return minCoins[change]

def printCoins(coinsUsed,change):
   coin = change
   while coin > 0:
      thisCoin = coinsUsed[coin]
      print(thisCoin)
      coin = coin - thisCoin

def main():
    amnt = 63
    clist = [1,5,10,21,25]
    coinsUsed = [0]*(amnt+1)
    coinCount = [0]*(amnt+1)

    print("Making change for",amnt,"requires")
    print(dpMakeChange(clist,amnt,coinCount,coinsUsed),"coins")
    print("They are:")
    printCoins(coinsUsed,amnt)
    print("The used list is as follows:")
    print(coinsUsed)

main()