java理解硬币变化递归
我试图使用递归来解决硬币兑换问题,遇到了下面的代码
问题:给定一些面额的无限硬币,计算它们形成给定数量硬币的方式
输入:
int[] coins = {1, 2};
int amount = 5;
int ways = change(amount, coins, coins.length - 1);
// expected ways = 3 --> 11111, 1112, 122
代码:
int change(int amount, int[] coins, int index) {
if (amount < 0) return 0;
if (amount == 0) return 1;
int ways = 0;
while (amount > 0 && index >= 0) {
ways += change(amount - coins[index], coins, index);
index = index - 1;
}
return ways;
}
我理解代码本身,也理解基本情况,但我无法理解它是如何封装递归/解决方案的
如果我在解factorial(n)
,我可以说factorial(n) = n * factorial(n-1)
,所以我可以清楚地“看到”递归。在换硬币的例子中,我无法推断出类似的关系。有人能帮我吗
# 1 楼答案
递归行在这里:
ways += change(amount - coins[index], coins, index);
我对代码做了一些注释来解释它
更明确地说: