我试图用递归来解决硬币兑换问题,遇到了下面的代码。
问题:给定一些面额的无限硬币,计算它们形成给定数量的方式。
输入:
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;
}
我理解代码本身,也理解基本情况,但是我不理解它是如何封装递归/解决方案的。
例如,如果我正在求解阶乘(n)
,我可以说阶乘(n)=n*阶乘(n-1)
,因此我可以清楚地“看到”递归。在换硬币的例子中,我无法推断出类似的关系。有人能帮我吗?
递归行在这里:ways=change(金额-硬币[索引]、硬币、索引)
我已经注释了代码来解释一下。
java prettyprint-override">//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]
给定一个值N,如果我们想改变为N美分,并且我们有无限量的S={S1,S2,...,Sm}值的硬币,我们有多少种方法可以改变?硬币的顺序并不重要。不过还有一个额外的限制:你只能用正好是K的硬币换零钱。 例如,对于N=4,k=2和S={1,2,3},有两个解:{2,2},{1,3}。所以输出应该是2。 解决方案: 以上是递归解决方案。但是,我需要有关动态规划解决方案的帮助: 让表示与元素和硬币的总和。
我需要编写一个算法,它接收一个数字和一个数字列表,并从列表中返回可能的数字组合的数量,从而可以创建和数。例如:def coin(5,[1,2,5,6]应该返回数字4,因为列表中有4种可能的组合可以一起创建数字5。下面是我尝试过的代码,但它不起作用。输出是6而不是4,我希望您能帮助我理解为什么。
我见过很多硬币更换问题,这个问题很独特。我尝试使用DP和递归,但我无法解决它。 这就是问题所在: 假设给定一个价格,X,其中X是美分,我有5种有限面额的硬币,1,5,10,20,50。我有不同数量的1、5、10、20、50分硬币。我想用最大数量的硬币来确定价格X。我该怎么做?(假设X总是可以用手头的硬币制作) 例如,如果价格X=52,并且 我有三枚一分硬币 我有四枚五分硬币 我有8枚10美分的硬币
问题:我很难找到达到特定金额所需的最低硬币数量。我很确定这是最简单的递归方式,使用动态编程方法,我基本上应该得到Math.min(“获取ACoin”、“离开ACoin”);不幸的是,我的代码不会终止,尽管我确实有在满足总和的条件下终止的if语句,硬币数组耗尽,或者如果总和结束。请查看下面的代码,让我知道我做错了什么,特别是为什么我的代码继续执行,直到它收到一个stackoverflow错误,尽管我
我目前正在尝试用Python实现动态编程,但我不知道如何设置回溯部分,使其不会重复排列。例如,一个输入应该是(6,[1,5]),预期的输出应该是2,因为有两种可能的方式来排列1和5,使它们的总和等于6。这些组合是{1,1,1,1,1}和{1,5}但是我的程序目前的工作方式,它考虑了上面显示的组合和组合{5,1}。这导致输出为3,这不是我想要的。所以我的问题是“如何防止重复排列?”。我当前的代码如下
我的硬币兑换动态编程实现在一些测试用例中失败,我很难找出原因: 问题陈述:给定一个数量和一个硬币列表,找出制造该数量所需的最小硬币数量。 例如: 目标金额:63 硬币列表:[1,5,10,21,25] 输出:[21,21,21] 小装饰品:https://trinket.io/python/43fcff035e