硬币找零复发解决方案

Question

给定一个值 N，如果我们想找 N 美分，并且我们有无限供应的每个 S = { S1, S2, .. , Sm} 值的硬币，我们有多少种方法可以找零改变？硬币的顺序没有 matter.There 是额外的限制：你只能找 K 个硬币。

例如，对于N = 4，k = 2和S = {1,2,3}，有两种解决方案：{2,2}，{1,3}。所以输出应该是 2.

解决方案：

int getways(int coins, int target, int total_coins, int *denomination, int size, int idx)
    {
            int sum = 0, i;
            if (coins > target || total_coins < 0)
                    return 0;
            if (target == coins && total_coins == 0)
                    return 1;
            if (target == coins && total_coins < 0)
                    return 0;
            for (i=idx;i<size;i++) {
                    sum += getways(coins+denomination[i], target, total_coins-1, denomination, size, i);
            }
            return sum;
    }

    int main()
    {
            int target = 49;
            int total_coins = 15;
            int denomination[] = {1, 2, 3, 4, 5};
            int size = sizeof(denomination)/sizeof(denomination[0]);
            printf("%d\n", getways(0, target, total_coins, denomination, size, 0));
    }

以上是递归求解。但是我需要有关我的动态编程解决方案的帮助：

设 dp[i][j][k] 表示 i 的总和 j 个元素和 k 个硬币。

所以，

dp[i][j][k] = dp[i][j-1][k] + dp[i-a[j]][j][k-1]

我的递归关系对吗？

Answer 1

我不太明白你的递归关系：

Let dp[i][j][k] represent sum up to i with j elements and k coins.

我认为你是在正确的轨道上，但我建议简单地删除中间维度 [j]，并使用 dp[sum][coinsLeft] 如下：

dp[0][0] = 1  // coins: 0, desired sum: 0  =>  1 solution
dp[i][0] = 0  // coins: 0, desired sum: i  =>  0 solutions

dp[sum][coinsLeft] = dp[sum - S1][coinsLeft-1]
                   + dp[sum - S2][coinsLeft-1]
                   + ...
                   + dp[sum - SM][coinsLeft-1]

然后在 dp[N][K] 找到答案（= 添加 K 个硬币以获得 N 的方法数分)

这里有一些示例代码（我建议你在尝试自己解决之前不要看它。这是一个很好的练习）：

public static int combinations(int numCoinsToUse, int targetSum, int[] denom) {
    // dp[numCoins][sum]  ==  ways to get sum using numCoins
    int[][] dp = new int[numCoinsToUse+1][targetSum];

     // Any sum (except 0) is impossible with 0 coins
     for (int sum = 0; sum < targetSum; sum++) {
         dp[0][sum] = sum == 0 ? 1 : 0;
     }

     // Gradually increase number of coins
     for (int c = 1; c <= numCoinsToUse; c++)
         for (int sum = 0; sum < targetSum; sum++)
             for (int d : denom)
                 if (sum >= d)
                     dp[c][sum] += dp[c-1][sum - d];
     return dp[numCoinsToUse][targetSum-1];
 }

Using your example input:

combinations(2, 4, new int[] {1, 2, 3} )  // gives 2

硬币找零复发解决方案

coin change recurrence solution

recurrence

dynamic-programming