理解硬币找零递归 [英] Understanding coin change recursion

问题描述

我试图专门使用递归来解决硬币找零问题，但遇到了以下代码.

I was trying to solve the coin change problem specifically using recursion, and came across the below code.

问题: 给定一些面额的无限硬币，计算编号.它们可以形成给定数量的方式.

Problem: Given infinite coins of some denominations, calculate the no. of ways the given amount can be formed by them.

输入:

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;
}

我了解代码本身，也了解基本情况，但我不明白它是如何封装递归/解决方案的.

I understand the code itself and I understand the base cases as well, but I am failing to understand how it encapsulates the recursion/solution.

例如.如果我正在解决factorial(n)，我可以说factorial(n) = n * factorial(n-1)，这样我就可以清楚地看到"递归.我无法在硬币变化示例中推断出类似的关系.有人能帮我解决这个问题吗?

Eg. If I am solving the factorial(n), I can say that factorial(n) = n * factorial(n-1), so I can clearly "see" the recursion. I am not able to deduce a similar relation in the coin change example. Can anyone help me with this?

推荐答案

递归行在这里:ways += change(amount -coin[index],coins,index);

我已经对代码进行了注释以对其进行解释.

I've commented the code to explain it a bit.

//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]

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