硬币变化递归方法 [英] 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.

这是我目前所拥有的:

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屋！