原问题

You are working at the cash counter at a fun-fair, and you have different types of coins available to you in infinite quantities. The value of each coin is already given. Can you determine the number of ways of making change for a particular number of units using the given types of coins?

For example, if you have 4 types of coins, and the value of each type is given as {8,3,1,2} respectively, you can make change for 3 units in three ways: {1,1,1},{1,2} and {3}.

https://www.hackerrank.com/challenges/coin-change/problem

思路

这明显是一道动态规划的问题,所以要找到sub-problem:
只用一枚coin, 找0元有几种解法? 找1元有几种解法?… 找 N元有几种解法?
再添加第二枚coin, 找0元有几种解法?(?+之前只用一枚coin的0元解法),…找 N元有几种解法??

假设一共有c枚硬币,需要找的值为n。我们可以维护一个c*(n+1)的数组 (注意数组下标为0,所以需要n+1)来保存各个阶段的结果, 当我们遍历完所有元素的时候,数组[c][n+1]的值就是我们需要的结果。接下来我们只要分析这些元素都是怎么填的。以原问题举例:

0123
[8]1000
[8,3]
[8,3,1]
[8,3,1,2]

首先,当只有[8]这枚硬币的时候,找0元有多少种方式?注意这里是1, 因为这种方式就是『不用任何硬币』。找1元有多少种方式?没有办法,所以只能是0,从1-7都是零。因为如果你用一枚价值为c的硬币,是无法给[1..c-1]的面额找零的。注意如果继续往后算到8,那这里又会是1,因此给8元找零,可以给一枚8元。你会发现,第一行的逻辑是,所有8的倍数,和0的位置会是1,其余位置都为0. 简单来说,就是
[1 if v % 8 == 0 else 0 for v in range(n+1)]

接下来我们继续算第二行,注意到这一行的硬币面值是3,仅仅使用3这枚硬币是没有办法给面额为1,2的钱找零的。但是!第二行的意义并不是仅仅使用3这枚硬币的解法,而是当仅仅使用3这枚硬币和之前所有硬币时的解法。因此,从第二行开始,如果当前下标值小于硬币值,这里需要填的数值就是照抄上一行。它的意思就是,仅仅使用当前这枚硬币是没有办法找零的,因此这里的数值就是0加上之前的硬币能提供的解法。

当下标大于或等于硬币值得时候,比如4, 那么一共的解法就是
不用当前硬币的解法+用当前硬币的解法
不用当前硬币的解法就是上一行的值。 如果使用当前硬币,那我们相当于把问题总额减少到n-3, 而这个解我们已经知道,就是本行下标[n-3]的值。

以此类推,我们可以获得表格所有值

0123
[8]1000
[8,3]1000+1=1
[8,3,1]10+1=10+1=11+1=2
[8,3,1,2]111+1=22+1=3
def getWays(n, c):
    # dp[n] stores the number of ways to change value n
    # 逻辑如下
    # dp[m][n] 代表 当只使用前m币种时,给n找零方式的种类, 比如币种为 {8,3,1,2}
    # dp[1][3] 代表,当使用{8,3} 币种时, 给3找零钱种类
    # 因此,我们可以建立一个len(c)*(n+1)的二维数组,而 dp[len(c)-1][n+1] 的数值就是结果 (注意数组下标为零)

    first = c[0]
    dp = [1 if v % first == 0 else 0 for v in range(n+1)]
    for coin_value in c[1:]:
        for v in range(0, n+1):
            if v >= coin_value:
                dp[v] += dp[v-coin_value]
    return dp[n]

Leave a Reply

Your email address will not be published. Required fields are marked *