Coin

出处

Given a value N, this N means we need to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change?

Solution

本问题以及其他类似描述的Coin Change问题,都属于典型的分布在二维整数空间上的计数问题,用DP。

重要的是理解如下递推关系:

对于第j种coin,无非是选择和不选择使用两种可能(i是目标钱数,j是当前coin的下标)

ways(i, j) = ways(i-s(j), j) + ways(i, j-1); i~[0,N], j~[1,m]

注意到在j这个维度上,只在意紧邻的上一步的结果,而不在意过去几步的结果,最后仍然是求和,因此上一步的局部解也只是当前解求和过程当中的一部分,完全可以覆盖,仅用一个变量表示,因此DP table可以简化为i方向一维空间。

Complexity

两层循环,时间复杂度 O(mn),空间复杂度 O(n)

Code

stepstr = input()
steps = stepstr.split()
test = int(input())

table = [[0 for x in range(len(steps))] for x in range(int(1E5+1))]
# Fill the enteries for 0 value case (n = 0)
for i in range(len(steps)):
    table[0][i] = 1

last = 1
for t in range(0,test):
    target = int(input())
 
    # Fill rest of the table enteries in bottom up manner
    for i in range(last, target+1):
        for j in range(len(steps)):
            # Count of solutions including S[j]
            x = table[i - int(steps[j])][j] if i-int(steps[j]) >= 0 else 0
 
            # Count of solutions excluding S[j]
            y = table[i][j-1] if j >= 1 else 0
 
            # total count
            table[i][j] = x + y
            table[i][j] %= 1E9+7;
    if (target > last):
        last = target
    print(int(table[target][len(steps)-1]))
 
int minNum(int[] S, int n) {
    int[] dp = new int[n+1];
    for (int i = 0; i < n+1; i++){
        dp[i] = Integer.MAX_INT;
    }
    dp[0] = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 0; j < m; j++){
            if (i >= s[j] && dp[i] > dp[i-s[j]]){
                dp[i] = dp[i-s[j]] + 1;
            }
        }
    }
    return dp[n];
}

Coin

Given an infinite number of quarters(25 cents), dimes(10 cents), nickels(5 cents), and pennies(1 cent), write code to calculate the number of ways of representing n cents.

Solution

// Use the solution from the book to help understanding
public static int makeChange(int amount, int[] cents, int index){
    if (index == cents.length - 1)
        return 1;
    int coin = cents[index];
    int ways = 0;
    for (int i = 0; i * coin <= amount; i++){
        int rest = amount - i * coin;
        ways += makeChange(rest, cents, index+1);
    }
    return ways;
}

public static int makeChange(int n){
    int[] cents = {25, 10, 5, 1};
    return makeChange(n, cents, 0);
}