每天一道编程题——换零钱的方法数

Code

给定数组arr，arr中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，在给定一个整数aim代表要找的钱，求换钱有多少种方法。
如
arr=[1,5,10,25],aim=0,返回1
arr=[1,5,10,25],aim=15,返回6
arr=[3,5],aim=2,返回0

暴力递归破解法

如果arr=[5,10,25,1],aim=15
1.用0张5元货币，让[10,25,1]组成剩下的15,最终方法数记为res1
2.用1张5元货币，让[10,25,1]组成剩下的10,最终方法数记为res2
3.用2张5元货币，让[10,25,1]组成剩下的5,最终方法数记为res3
4.用3张5元货币，让[10,25,1]组成剩下的0,最终方法数记为res4

1
2
3
4
res1:2(0*5+15*1;0*5+1*10+1*5)
res2:2(1*5+10*1;1*5+1*10)
res3:1(2*5+5*1)
res4:1(3*5)

答案就是res1+res2+res3+res4
缺点：
大量重复计算。
规模小的时候还好，一旦规模大了。
比如aim=1000，对于05+110和25+010，后续的计算都是一样的，求[25,1]组合剩下的990的方法总数。

复杂度：

O(aim^N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
arr = [5, 10, 25, 1]
aim = 15
def naive_res_conis(arr, aim):
    def r(arr, aim, index):
        res = 0
        if index == len(arr):
            res = 1 if aim == 0 else 0
        else:
            i = 0
            while arr[index] * i <= aim:
                res += r(arr, aim - arr[index] * i, index + 1)
                i += 1
        return res
    return r(arr, aim, 0)

经过记忆搜索优化的暴力递归

又如上面aim=1000的例子。
对于0*5+1*10和2*5+0*10，他们调用递归函数时候传入的参数，arr,aim,index都是相同的，也就是说我们可以利用这一性质去除重复的计算。
记忆搜索优化是针对暴力递归最初级的优化技巧，分析递归函数的状态可以由那些变量表示，做出相应维度和大小的cache即可。

复杂度:

O(N*aim^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
from functools import wraps
def memo(func):
    cache = {}
    @wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap
def memo_res_conis(arr, aim):
    arr = arr
    @memo
    def r(aim, index):
        res = 0
        if index == len(arr):
            res = 1 if aim == 0 else 0
        else:
            i = 0
            while arr[index] * i <= aim:
                res += r(aim - arr[index] * i, index + 1)
                i += 1
        return res
    return r(aim, 0)
# ++++++++++++++++++++TEST++++++++++++++++++++++++++
'''
import time
aim=500
begin=time.time()
print memo_res(arr,aim)
print time.time()-begin
begin=time.time()
print naive_res(arr,aim)
print time.time()-begin
'''
# 结果
'''
19006
0.018000125885
19006
1.15899991989
'''
# ++++++++++++++++++++TEST END+++++++++++++++++++++++

关于记忆搜索优化，可见记忆体化的装饰器。

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
dp[i][j]的含义，在可以任意使用arr[0...i]货币的情况下，组成j有多少种方法。
dp[...][0]:组成钱为0的方法数，全部置1
dp[0][...]:只能使用arr[0]的货币的情况下，组成钱的方法数
dp[1][...]:只能使用arr[0]与arr[1]的货币的情况下，组成钱的方法数
假设计算到位置(i,j),dp[i][j]的值可能来自下面的情况
1.完全不使用当前货币arr[i]的情况,即dp[i-1][j]
2.使用1张货币arr[i]的情况,即dp[i-1][j-arr[i]]
3.使用2张货币arr[i]的情况,即dp[i-1][j-2*arr[i]]
....
k+1.使用k张货币arr[i]的情况,即dp[i-1][j-k*arr[i]] (j-k*arr[i]>=0)
#### 复杂度：
枚举dp[i-1][0...j]上的所有值，dp一共有N*aim个
O(N*aim^2)
本质上，动态规划等价于记忆化搜索方法。
记忆话搜索的方法说白了就是不关心到达某一个递归过程的路径，只是单纯地对计算过的递归过程进行记录，避免重复的递归。
动态规划的方法则是规定好每一个递归过程的计算顺序，一次进行计算，后计算的过程严格依赖前面计算的过程。
动态规划规定计算顺序，而记忆搜索不用规定。
各有各的优势
动态规划可以将递归变为迭代。
记忆搜索面对某些情况，如arr=[20000,10000,1000],aim=2000000000的情况有优势
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def dp_coins(arr, aim):
    n = len(arr)
    dp = [[0] * (aim + 1) for i in range(n)]
    # 第一列全部置1
    for i in range(n):
        dp[i][0] = 1
    # 初始化第一行
    j = 0
    while arr[0] * j <= aim:
        dp[0][arr[0] * j] = 1
        j += 1
    for i in range(1, n):
        for j in range(1, aim + 1):
            num, k = 0, 0
            while arr[i] * k <= j:
                # k=0时,也就是dp[i-1][j],也就是上一个元素
                # k=1时,也就是使用一张arr[i]货币的情况
                num += dp[i - 1][j - arr[i] * k]
                k += 1
            dp[i][j] = num
    return dp[-1][-1]

动态规划的优化（什么？还能优化？）

我们将目光放在前一个算法的第二个while循环里面。
本质上，while里面的枚举可以化简为dp[i][j]=dp[i-1][j]+dp[i][[j-arr[i]] (上边的加上左边的)
如，

1
2
3
arr = [5, 10, 25, 1]
aim = 25
![1][25]=dp[0][25](./每天一道编程题——换零钱的方法数只用5块)+dp[i][[j-arr[i]](用5块跟10块组成j-arr[i]元的方法数)

复杂度:

O(N*aim)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def dp_coin2(arr, aim):
    n = len(arr)
    dp = [[0] * (aim + 1) for i in range(n)]
    # 第一列全部置1
    for i in range(n):
        dp[i][0] = 1
    # 初始化第一行
    j = 0
    while arr[0] * j <= aim:
        dp[0][arr[0] * j] = 1
        j += 1
    for i in range(1, n):
        for j in range(1, aim + 1):
            dp[i][j] = dp[i - 1][j]
            dp[i][j] += dp[i][j - arr[i]] if j - arr[i] >= 0 else 0
    return dp[-1][-1]

空间压缩

将空间复杂度降为O(aim)

1
2
3
4
5
6
7
8
9
10
11
12
13
def dp_coin3(arr, aim):
    n = len(arr)
    dp = [0 for i in range(aim + 1)]
    # 初始化第一行
    j = 0
    while arr[0] * j <= aim:
        dp[arr[0] * j] = 1
        j += 1
    for i in range(1, n):
        for j in range(1, aim + 1):
            dp[j] += dp[j - arr[i]] if j - arr[i] >= 0 else 0
    return dp[-1]
print dp_coin3(arr, aim)

本文标题:每天一道编程题——换零钱的方法数

文章作者:Vincent Zhong

发布时间:2016-10-17, 21:18:20

最后更新:2019-07-07, 13:13:10

原始链接:https://wax8280.github.io/2016/10/17/每天一道编程题——换零钱的方法数/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 暴力递归破解法
    1. 1.1. 复杂度：
  2. 2. 经过记忆搜索优化的暴力递归
    1. 2.1. 复杂度:
  3. 3. 动态规划
  4. 4. 动态规划的优化（什么？还能优化？）
    1. 4.1. 复杂度:
  5. 5. 空间压缩
|