理解硬币变化递归
Understanding coin change recursion
我试图专门使用 递归 来解决硬币找零问题,并遇到了以下代码。
问题:给定一些面额的无限硬币,计算第几枚。给定量可以由它们形成的方式。
输入:
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;
}
我理解代码本身,也理解基本情况,但我不明白它是如何封装 recursion/solution。
例如。如果我正在解决 factorial(n)
,我可以说 factorial(n) = n * factorial(n-1)
,所以我可以清楚地“看到”递归。我无法在硬币找零示例中推断出类似的关系。谁能帮我解决这个问题?
递归行在这里:ways += change(amount - coins[index], coins, index);
我对代码进行了注释以对其进行一些解释。
//amount is the total value we want all our coins to add up to
//coins carries the values we can add up to get the amount
//index is the coin we're "on" right now - we'll explain this more in a bit
int change(int amount, int[] coins, int index) {
//we went too low: out last coin was too large and pushed us into negatives
if (amount < 0) return 0;
//exact change! we found a new way to make change with these coins
if (amount == 0) return 1;
//count the number of ways we can make the change
int ways = 0;
//here's where the recursion starts: we start at index, which is the number of
//coins available to us. in this case, we're going right to the end of the
//array to the "2" coin. we'll repeatedly subtract "2" from the amount until
//we hit 0, meaning we were able to meet the amount using only "2" coins, or
//we're unable to go any further.
//if we're unable to go further, we return one level up from the recursion,
//and decrease index by 1: this means we're now trying the "1" coin.
//this process repeats, making as much change with the "2" coin as we can and
//falling back to the "1" coin when we get stuck or reach the bottom of the
//recursion.
while (amount > 0 && index >= 0) {
//try to use this same coin over and over, and when the function returns,
//whether through success or failure...
ways += change(amount - coins[index], coins, index);
//...move onto the next coin and repeat the process.
index = index - 1;
}
//the total number of times we were able to make exact change with these coins
return ways;
}
通俗地说:
desired value: 5 available coins: 1, 2
value = 5
coin = 2
5 - 2 = 3
. value = 3
. coin = 2
. 3 - 2 = 1
. . value = 1
. . coin = 2
. . 1 - 2 = -1 | fail
. . coin = 1
. . 1 - 1 = 0 | success
. . no more coins to try
. value = 3
. coin = 1
. 3 - 1 = 2
. . value = 2
. . coin = 1
. . 2 - 1 = 1
. . . value = 1
. . . coin = 1
. . . 1 - 1 = 0 | success
. . . no more coins to try
. . no more coins to try
. no more coins to try
value = 5
coin = 1
5 - 1 = 4
. value = 4
[...and so on]
我试图专门使用 递归 来解决硬币找零问题,并遇到了以下代码。
问题:给定一些面额的无限硬币,计算第几枚。给定量可以由它们形成的方式。
输入:
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;
}
我理解代码本身,也理解基本情况,但我不明白它是如何封装 recursion/solution。
例如。如果我正在解决 factorial(n)
,我可以说 factorial(n) = n * factorial(n-1)
,所以我可以清楚地“看到”递归。我无法在硬币找零示例中推断出类似的关系。谁能帮我解决这个问题?
递归行在这里:ways += change(amount - coins[index], coins, index);
我对代码进行了注释以对其进行一些解释。
//amount is the total value we want all our coins to add up to
//coins carries the values we can add up to get the amount
//index is the coin we're "on" right now - we'll explain this more in a bit
int change(int amount, int[] coins, int index) {
//we went too low: out last coin was too large and pushed us into negatives
if (amount < 0) return 0;
//exact change! we found a new way to make change with these coins
if (amount == 0) return 1;
//count the number of ways we can make the change
int ways = 0;
//here's where the recursion starts: we start at index, which is the number of
//coins available to us. in this case, we're going right to the end of the
//array to the "2" coin. we'll repeatedly subtract "2" from the amount until
//we hit 0, meaning we were able to meet the amount using only "2" coins, or
//we're unable to go any further.
//if we're unable to go further, we return one level up from the recursion,
//and decrease index by 1: this means we're now trying the "1" coin.
//this process repeats, making as much change with the "2" coin as we can and
//falling back to the "1" coin when we get stuck or reach the bottom of the
//recursion.
while (amount > 0 && index >= 0) {
//try to use this same coin over and over, and when the function returns,
//whether through success or failure...
ways += change(amount - coins[index], coins, index);
//...move onto the next coin and repeat the process.
index = index - 1;
}
//the total number of times we were able to make exact change with these coins
return ways;
}
通俗地说:
desired value: 5 available coins: 1, 2
value = 5
coin = 2
5 - 2 = 3
. value = 3
. coin = 2
. 3 - 2 = 1
. . value = 1
. . coin = 2
. . 1 - 2 = -1 | fail
. . coin = 1
. . 1 - 1 = 0 | success
. . no more coins to try
. value = 3
. coin = 1
. 3 - 1 = 2
. . value = 2
. . coin = 1
. . 2 - 1 = 1
. . . value = 1
. . . coin = 1
. . . 1 - 1 = 0 | success
. . . no more coins to try
. . no more coins to try
. no more coins to try
value = 5
coin = 1
5 - 1 = 4
. value = 4
[...and so on]