[TOC]

找零

用最少的硬币

1、如果当前剩余找零金额等于已有硬币面额，递归返回

2、拆分，按照硬币面额，先给一枚硬币，余下金额继续递归

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
# 动态规划：找零
def recMC(coinValueList,change):
    minCoins = change
    if change in coinValueList:
        return 1
    else:
        for coin in [c for c in coinValueList if c<=change]:
            numCoins = 1+recMC(coinValueList,change-coin)
            if numCoins<minCoins:
                minCoins = numCoins
        return minCoins

def recDC(coinValueList,change,knownResults):
    minCoins = change
    if knownResults[change]>0:
        return knownResults[change]

    if change in coinValueList:
        knownResults[change] = 1
        return 1
    else:
        for coin in [c for c in coinValueList if c<=change]:
            if knownResults[change]>0:
                numCoins = knownResults[change]
            else:
                numCoins = 1+recMC(coinValueList,change-coin)
            if numCoins<minCoins:
                minCoins = numCoins
        knownResults[change] = minCoins
    return minCoins

def dpMakeChange(coinValueList,change):
    minCoins = [0]*(change+1)
    for cents in range(change+1):
        minCoins[cents] = cents
        for coin in [c for c in coinValueList if c<=cents]:
            numCoins = minCoins[cents-coin]+1
            if numCoins<minCoins[cents]:
                minCoins[cents] = numCoins
    return minCoins[change]

def dpMakeChange_evol(coinValueList,change):
    minCoins = [0] * (change + 1)
    coinUsed = [0] * (change + 1)
    for cents in range(1,change + 1):
        minCoins[cents] = cents+1
        for coin in [c for c in coinValueList if c <= cents]:
            numCoins = minCoins[cents - coin] + 1
            if numCoins < minCoins[cents]:
                minCoins[cents] = numCoins
                coinUsed[cents] = coin
    return minCoins[change]