硬币找零递归方法 [英] Coin change recursive approach

问题描述

我正在尝试使用递归方法来解决硬币找零问题.问题是这样的:

I am trying to solve the coin change problem using a recursive approach. The problem goes like this:

您会得到不同面额的硬币和总金额.编写一个函数来计算组成该数量的组合的数量.

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount.

为您提供了一定数量的硬币.

You are given an amount and an array of coins.

这是我到目前为止所拥有的:

Here is what I have so far:

private static int[] coins = {1,2,5};

public static void main(String[] args) {
    System.out.println(count(13));
}

public static int count(int n)
{
    // If n is 0 then there is 1 solution
    if (n == 0)
        return 1;
     
    // If n is less than 0 then no solution exists
    if (n < 0)
        return 0;
 
    return count(n - coins[0]) + count(n - coins[1]) + count(n - coins[2]);
}

执行此操作时，我无法获得正确的组合.我认为问题在于退货，但我不知道为什么.在这里，我从金额中减去硬币，然后每次将它们加在一起.当它为0时，返回1.

When I do this I get nothing close to the right combinations. The problem I think is with the return but I can not figure out why. Here I am subtracting the coin from the amount and adding them together each time. When it gets 0 it returns 1.

推荐答案

首先，您应该替换:

return count(n - coins[0]) + count(n - coins[1]) + count(n - coins[2]);

带有循环:

int nCoins = 0;
for(int coin=0; coin<coins.length; coin++)
{
    nCoins += count(n-coins[coin]);
}
return nCoins;

这样做的麻烦是它将生成硬币的所有排列(= 634).要获得硬币的每种独特组合，您需要确保从当前硬币开始每个递归级别.为此，您需要在count方法中添加一个参数，以指示在钱币数组中开始的位置.

The trouble with this is that it'll generate all permutations of coins (=634). To get each unique combination of coins you need to make sure you start each level of recursion at the current coin. For this you need to add an argument to your count method, to indicate the position in the coin array at which to start.

public static int count(int n, int startCoin)

然后您的循环变为

int nCoins = 0;
for(int coin=startCoin; coin<coins.length; coin++)
{
    nCoins += count(n-coins[coin], coin);
}
return nCoins;

哪个给出正确答案(14).

Which gives the correct answer (14).

这篇关于硬币找零递归方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！