找钱问题--动态规划一例

Feb 16, 2011

用无限多的面值为 S = {S1, S2, …, Sm} 的分币，表示一个特定的分值n，有多少种方法？这个就是找钱问题 (Coin Change Problem)。

比如，用 1美分和 5 美分，表示7美分，有2种方法，第一种是1个5美分，2个1美分；第二种是7个1美分。

因为顺序对结果没有影响，即“1个5美分，2个1美分”和“2个1美分，1个5美分”是一样的，我们限定 S1 < S2 < … < Sm。用递归的方法，解法的数量 C(n, m)，可以分成2类：

一类是表示方法里不需要 Sm的，另一类是表示方法里需要Sm的。如上面的例子，一类表示是需要5美分，另一类不需要。

于是，递归公式如下：

C(n, m) = C(n, m-1) + C(n-Sm, m)

Python代码：

def count1(n,m):
    global numCalls
    numCalls += 1
    global S
    if n == 0:
        return 1
    if n < 0:
        return 0
    if m == 1:
        return 1
    return count1(n, m-1) + count1(n-S[m-1],m)

S = (1,5,10,25)
numCalls = 0
print count1(100,len(S))
print numCalls

count1()函数的运行结果是242，即用 1美分，5美分，10美分和25美分表示100美分有242种方法。 numCalls是13927，说明count1()函数被调用了13927次。这是因为我们重复计算了很多相同的中间结果。

这个问题可以用动态规划 (Dynamic Programming)来解决，关于动态规划推荐看 MIT 6.00 Introduction to Computer Science and Programming Lec 13。

动态规划应用于以下情况：子问题的最优解也是整体问题的最优解，同时子问题有重叠。那么就可以把子问题的解保存起来，只需要计算一次就可以。

于是：

def count(n,m):
    global numCalls
    numCalls += 1
    global S
    global memo
    try:
        return memo[(n,m)]
    except KeyError:
        if n == 0:
            memo[(n,m)] = 1
            return 1
        if n < 0:
            memo[(n,m)] = 0
            return 0
        if m == 1:
            memo[(n,m)] = 1
            return 1
    memo[(n,m)] = count(n, m-1) + count(n-S[m-1],m)
    return memo[(n,m)]

S = (1,5,10,25)
memo = {}
numCalls = 0
print count(100,len(S))
print numCalls

count()函数和count1()函数的唯一区别就是count()函数用一个字典 memo 记录了子问题的解。因此运行结果是一样的，都是242；但是numCalls是285，说明count()函数仅被调用了285次。这就是动态规划保存子问题的解的神奇结果。

azalea says

找钱问题--动态规划一例