硬币变化递归解

Question

给定一个值N，如果我们想改变为N美分，并且我们有无限量的S={S1，S2，...，Sm}值的硬币，我们有多少种方法可以改变？硬币的顺序并不重要。不过还有一个额外的限制：你只能用正好是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

我不太明白你的重复关系：

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

我认为您的思路是正确的，但我建议您只需删除中间维度[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];
 }
使用示例输入：