递归硬币兑换问题--计数排列
递归硬币兑换问题是一个经典的动态规划问题，其目标是找出给定金额的硬币兑换方式的总数。假设有不同面额的硬币，我们需要确定兑换给定金额所需的最少硬币数量。
递归硬币兑换问题的解决方案可以通过递归函数来实现。以下是一个完善且全面的答案：
概念： 递归硬币兑换问题是指给定一定面额的硬币和一个目标金额，求出兑换该目标金额所需的最少硬币数量。
分类： 递归硬币兑换问题属于动态规划问题的一种，可以通过递归函数和记忆化搜索来解决。
优势： 递归硬币兑换问题的优势在于可以通过递归函数的方式简洁地解决问题，并且可以通过记忆化搜索来提高计算效率。
应用场景： 递归硬币兑换问题可以应用于货币兑换、找零等场景，例如在商场购物时需要找零，或者在旅行中需要兑换不同国家的货币。
推荐的腾讯云相关产品和产品介绍链接地址： 腾讯云提供了多种云计算相关产品，以下是一些推荐的产品和其介绍链接地址：
- 云服务器（CVM）：提供弹性计算能力，支持多种操作系统和应用场景。详情请参考：https://cloud.tencent.com/product/cvm
- 云数据库 MySQL 版（CDB）：提供高性能、可扩展的关系型数据库服务。详情请参考：https://cloud.tencent.com/product/cdb_mysql
- 云原生容器服务（TKE）：提供高度可扩展的容器化应用管理平台。详情请参考：https://cloud.tencent.com/product/tke
- 人工智能平台（AI Lab）：提供丰富的人工智能开发工具和服务，包括图像识别、语音识别、自然语言处理等。详情请参考：https://cloud.tencent.com/product/ailab
- 物联网开发平台（IoT Explorer）：提供全面的物联网解决方案，包括设备接入、数据管理、应用开发等。详情请参考：https://cloud.tencent.com/product/iothub
总结： 递归硬币兑换问题是一个经典的动态规划问题，可以通过递归函数和记忆化搜索来解决。腾讯云提供了多种云计算相关产品，包括云服务器、云数据库、云原生容器服务、人工智能平台和物联网开发平台等，可以满足各种云计算需求。
相关·内容
1回答
我有一个低效的递归硬币兑换函数，它计算出给定数量的硬币组合的数量。如果可能的话，我想把它转换成一个更有效的迭代函数。
一个问题是，我正在使用回溯在一个称为面额的数组中尝试不同的硬币。我也在使用memoization，但当数量很大时，它不会加快速度。
下面是我的代码：
unsigned long long CalculateCombinations(std::vector<double> &denominations, std::vector<double> change,
double amount, unsigned int index)
{
浏览 2提问于2018-06-21得票数 0
2回答
我写的代码使用动态编程解决了基本的硬币兑换问题，并给出了进行兑换所需的最小硬币数量。但是我想用最小的数字来存储每个硬币扮演角色的数量。
我尝试做的是初始化一个数组count[]，就像散列一样，只要找到min，coin[j]的数量就会递增，也就是count[coin[j]]++。但这并不是我想要的工作方式，因为它在每次找到与coin[j]对应的min时都会添加硬币。因此，这个数字不是最终答案中的硬币的最终计数。
代码如下：
void makeChange(int coin[], int n, int value)
{
int i, j;
int min_coin[MAX];
浏览 6提问于2014-05-09得票数 1
我已经实现了货币兑换问题，例如，用尽可能少的硬币兑换一定数量的货币。可用的面值有:1、3和4。即使是像100这样的小数目也需要很长时间。复杂度是2^n吗？
def moneychange_rec(money,coins):
if money == 0:
return table[money]
else:
for coin in coins:
if money>=coin:
table[money] = min(table[money],1 + moneychange_rec(money-coin,
浏览 0提问于2020-05-15得票数 0
1回答
我有兴趣解决硬币兑换问题的一个变体。回顾一下硬币兑换问题的正式定义：
给定一个值N，如果我们想改变N美分，并且我们有无限供应的S= {S1，S2，.，Sm)整值硬币，我们能用多少种方法来改变呢？硬币的顺序并不重要。例如，对于N=4和S= {1,2,3}，有四个解：{1，1，1}，{1,1,2}，{2,2}，{1,3}。对于N= 10和S= {2，5，3，6}，有五种解：{2，2，2，2}，{2，2，3}，{2,2,6}，{2,3,5}和{5,5}。因此，更详细的输出应该是5.。
，我们可以为这个问题找到一个基于表格DP的解决方案.此解决方案基于以下重复关系：
count(S, m, n) =
浏览 1提问于2018-01-24得票数 2
有很多硬币兑换的问题和答案，但我找不到这个，我想知道这是否甚至是一个硬币兑换问题。
基本上，我有一堆不同的硬币，每个硬币的数量都是无限的。
所以说，这里有各种各样的教派。每个堆栈都是无限的。( 25c硬币的数目是无限的，2c硬币的数目是无限的)。
然而，在每一叠硬币的顶部是一个特殊的硬币，其价值大于(或等于)以下硬币。如果不使用上面的硬币，我就无法进入下面的硬币。
我想找出的是一定数量的硬币的最低数量。
我认为这是可解决的动态规划，但我不知道如何在传统的解决方案中添加这个限制。
我在想，一旦我使用了特殊的硬币，用普通的硬币来代替它，我是否应该删除它，但我似乎无法推理，这是否会破坏算法。
浏览 6提问于2015-10-24得票数 1
回答已采纳
1回答
硬币兑换问题的简单DP解决方案使用一个大小为SUM的一维数组，并将其从0填充到SUM。基于递归NUMBER_OF_COINS = min(arraysum-coin1+1，arraysum-coin2...)。我写的代码是这样的。 def DynamicChange(money, coins):
if money<=0:
return 0
arr = [0]*(money+1)
for m in range(1, money+1):
arr[m] = 9999999
for coin in coins:
浏览 17提问于2020-09-24得票数 0
3回答
我已经在网站上查看过各种问题，也没有找到通过以下推理实现这一点的任何东西(所以我希望这不是一个副本)。
我试图通过C程序解决的问题如下：
作为自动售货机控制器的程序员，您需要计算组成所需更改的硬币的最小数量，以回馈客户。解决这一问题的有效方法是采用动态规划方法，首先计算1美分兑换所需的硬币数量，然后再计算2美分，然后再计算3美分，直到达到所需的变化为止，每次都使用先前计算的硬币数量。编写一个包含函数ComputeChange()的程序，其中包含有效硬币和所需更改的列表。此程序应从控制台反复请求所需的更改，并相应地调用ComputeChange()。它还应该使用“缓存”，其中任何先前计算过的中
浏览 8提问于2016-02-03得票数 15
回答已采纳
4回答
我试图用递归的方法来解决硬币的变化问题。问题是这样的：
你会得到不同面额的硬币和一笔钱。编写一个函数来计算组成该数量的组合数。
你会得到一笔钱和一批硬币。
以下是我到目前为止所拥有的：
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
浏览 2提问于2017-07-30得票数 3
回答已采纳
2回答
我在这里遇到了一个硬币找零问题的解决方案：。在这里，我能够理解第一种递归方法，第二种方法，它使用DP和2D数组。但我不能理解第三种解决方案背后的逻辑。
据我所知，最后一种方法适用于考虑硬币兑换时使用的硬币顺序的问题。我说的对吗？如果我错了，有人能给我解释一下吗？
浏览 0提问于2015-11-20得票数 1
1回答
我有一个赋值函数，它只接收一个整数和一个整数列表(不能添加任何其他内容)。它应该返回列表中和为k的组合的数量，顺序并不重要(硬币兑换问题)。此外，我还需要使用递归。下面是我所做的： def coin(k, lst):
if k == 0:
return 1
if k < 0:
return 0
else:
sum = 0
for i in range(len(lst)):
sum += coin(k - lst[i], lst)
return sum 问题是它
浏览 19提问于2021-04-24得票数 0
3回答
我试着解决硬币兑换问题。你得到了一笔钱(例如55美分)，并且必须尽可能少地归还硬币。
我的解决方案非常简单(而且可能效率极低)。我试着用蛮力做这件事。
首先，我试着用硬编码的固定硬币来做，而且效果很好。
money = 55
def findMinCoins(money):
nq = int(money/25)
nd = int(money/10)
nc = int(money/1)
smallest = nq + nd + nc
for q in range(nq+1):
for d in range(nd+1):
浏览 4提问于2019-10-19得票数 1
回答已采纳
2回答
因此，典型的硬币兑换问题要求您找出是否可以使用面额为x1，x2，...，xn的无限硬币来改变值v，但我想知道您如何使用每枚硬币最多一次来解决相同的问题？
对于最初的问题，我知道你可以迭代值的前缀，看看是否可以改变v-x_i，但是当它被限制为每个面额最多一个硬币时，我就不知所措了。
有什么建议可以帮我入门吗？我可能在想，你也可以遍历面额的前缀。不过我不确定。
浏览 0提问于2013-01-23得票数 0
我理解硬币兑换问题的贪婪算法是如何工作的(用最少可能的硬币支付特定的金额)-它总是选择面额最大但不超过剩余金额的硬币-并且它总是为特定的硬币组找到正确的解决方案。
但对于一些硬币组，贪婪算法对某些和是无效的。例如，对于集合{1, 15, 25}和总和30，贪婪算法首先选择25，剩余5，然后选择五个1，总共六个硬币。但硬币数量最少的解决方案是选择15两次。
一组硬币必须满足什么条件才能使贪婪算法找到所有和的最小解？
浏览 7提问于2012-11-26得票数 84
4回答
只要一美元，就把它兑换成欧元硬币和纸币。你得到了美元的数额作为论据，并说美元对欧元的汇率是1.30。欧元面额是500张，200张，100张，50张，20张，10张，5张，2张，1张，50美分，25美分，10美分，5美分，2美分，1美分。把那一美元兑换成最少的纸币和硬币。(将一美元数字(如$10.00)换算为欧元票据和硬币中的等值数额。)
免责声明:这是我的作业问题。。
我考虑过用一个while循环来解决这个问题，这个循环会遍历每个面额，并从值中减去它。类似于：
while(amount > 0){
if(amount - denomination[index] > 0)
浏览 1提问于2019-09-05得票数 0
回答已采纳
我想知道硬币兑换问题的算法思想，其中每个面额都有无限个硬币。表示如何应用DP (如标准硬币更换问题)，例如在集合1、10、15中，35个硬币的零钱--2枚10枚硬币和1枚15枚硬币
也给我一个关于这方面的蛮力算法的想法。我知道要遍历所有的集合。但是如何在暴力逼迫下改变每枚硬币的数量呢？
浏览 5提问于2009-10-05得票数 2
回答已采纳
希望你们今天过得愉快！
我喜欢编程，但在过去的几天里，我有失眠的夜晚，CodeChef总是在我的动态编程解决方案上返回SIGSEGV错误。
我现在正在解决问题。问题是-
在拜特兰德，他们有一个非常奇怪的货币体系。每枚拜占庭金币上都写着一个整数。一个硬币n可以在银行里兑换成三个硬币: n/2、n/3和n/4。但是这些数字都是四舍五入的(银行必须盈利)。你也可以以美元出售拜占庭硬币。汇率是1:1，但你不能买拜占庭硬币。你有一枚金币。你能得到多少美元？
输入
输入将包含几个测试用例(不超过10个)。每个测试用例都是一行，编号为n，0 <= n <= 1 000 000 000。这是你硬
浏览 4提问于2015-12-18得票数 0
回答已采纳
我了解硬币兑换问题的贪婪算法是如何工作的。我只是有点困惑，什么时候输出总是最优的(当使用贪婪的时候)，什么时候贪婪的总是失败。
例如，美国硬币的面额是规范的，意味着它总是最优的，什么硬币面额将总是失败或总是最优的？
浏览 7提问于2021-11-13得票数 0
所以我在python中递归地做最小硬币兑换问题。我想要可视化它进行了多少次递归调用。因此，我在函数中添加了一个"print 'recursion'“。但是现在它是连续的打印递归，没有到达输出，程序甚至没有停止。这是程序。
def min_coins(coins, change):
print 'recursion' #program works without this line
mincoins = change
if change in coins:
return 1
else:
for
浏览 0提问于2016-02-01得票数 0
我对C#非常陌生，我有一个递归问题要解决。我想在这个硬币兑换问题中得到尽可能少的硬币。我已经对算法进行了调整，但我需要返回一个类型更改的对象，该对象将包含尽可能少的组合。
我试图实现一个算法，但我有所有可能的组合。
using System;
using System.Collections.Generic;
using System.Linq;
// Do not modify change
class Change
{
public long coin2 = 0;
public long bill5 = 0;
public long bill10 = 0;
}
浏览 0提问于2019-02-15得票数 3
2回答
我试图解决一个经典的动态规划硬币变化问题。这是一个家庭作业问题，我并不是在寻找完整的解决方案，只是为了看看我做错了什么。
输入：
我们想用硬币支付一定价值的x金额。
集合d表示可用的面额硬币数(1c，5c，10c，25c，100c，200c)
输出：
最低数量的硬币，需要交换的手付款。
假设：
收银机操作员有无限的硬币供应，并知道如何给出最佳的变化。
到目前为止，我试图做的是：
我正在尝试构建一个数组C，这样每个元素Ci都是用来交换数量i的/最小/数量的硬币。
C=0
对于Ci，我通过取所有Ci-di加1的最小值来计算，对于所有可用的硬币面额。然后我从可
浏览 5提问于2012-07-03得票数 7
2回答
我有无限四种硬币的百分比: 1，5，25，50。如何挑选精确的48个硬币来进行1美元的精确兑换？(以任何一种有效的方式)
我知道如何递归地解决这个问题，但是是否可以使用DP来解决这个问题呢？多么?谢谢!
浏览 5提问于2015-11-08得票数 1
回答已采纳
3回答
给定一组整数1,2和3，找出这些整数可加为n的方法的数目。(顺序重要，例如n是5，1+2+1+1和2+1+1+1是两个不同的解)
我的解决方案是将n分裂成一个1s的列表，所以如果n= 5，A=1，1，1，1，我将通过添加相邻数来递归地从每个列表中生成更多的子列表。因此，A将再生成4个列表: 2,1,1,1，1，1，1，1，1，1，2，2，1，1，2，每个列表都会生成更多的子列表，直到达到3,2或2,3这样的终止情况为止。
下面是我建议的解决方案(用Python)
ways = []
def check_terminating(A,n):
# check for terminating
浏览 2提问于2017-08-16得票数 1
回答已采纳
我现在正在研究Leetcode 322。硬币兑换，问题如下：
给您一个表示不同面值的硬币的整数数组硬币和一个代表总金额的整数数量。
归还最少数量的硬币，你需要弥补这个数额。如果这个数额的钱不能由任何组合的硬币，回报-1。
你可以假设你有无限数量的每一种硬币。
示例1：
输入:硬币= 1,2,5，数量= 11输出:3解释: 11 =5+5+1
示例2：
输入:硬币= 2，数量=3输出：-1
例3：
输入:硬币= 1，数量=0输出:0
例4：
投入:硬币= 1，数量=1输出:1
例5：
投入:硬币= 1，数量=2输出:2
我试着通过自上而下的DP记忆来解决这个问题。我在helper函数中设置了一
浏览 5提问于2021-04-13得票数 0
回答已采纳
1回答
我知道如何使用命令式编程和DP解决硬币更改问题。
我知道如何用FP和非尾递归来解决硬币变化问题。但是它会多次计算相同的问题，从而导致效率低下。
我知道如何用FP和DP/tail递归来计算斐波纳契数。许多文章使用这个例子来解释"FP可以与DP“”和“结合起来，递归也可以和循环”“一样高效。
但是我不知道如何用FP和DP/tail递归来解决硬币变化问题。
我认为奇怪的是，关于命令式编程的文章总是多次提到计算相同问题的效率低下的问题，而FP上的文章则忽略了这一点。
在更一般的意义上，我想知道FP是否足够强大来解决这样的“二维”问题，而fibonacci是一个“一维”问题。有人能帮我吗？
硬币
浏览 1提问于2015-04-26得票数 0
1回答
我是Prolog的新手，我想编写一个函数，返回每美元(100美分)进行更改的所有不同方式。我们有2美分硬币，11美分硬币，38美分硬币，有趣的是-8美分硬币(一枚价值-8美分的硬币)。另外，我们总共只有10枚"-8“硬币。(其他硬币无上限)
以下是我的尝试：
change100([P2, P11, P38, Pn8]):-
Pn8 =< 10,
Pn8 >= 0,
P2 >= 0, P11 >= 0, P38 >= 0,
D is 2 * P2 + 11 * P11 + 38 * P38 - 8 * Pn8,
D
浏览 1提问于2014-03-19得票数 1
3回答
我正试图在CodeChef：上解决这个问题
但是当我提交我的代码时，显然需要很长时间才能执行，并且说时间已经过期了。我不确定我的代码是否效率低下(在我看来不是这样)，或者如果我对I/O有问题，有一个9秒钟的时间限制，以解决最大10个输入，0 <= n <= 1 000 000 000。
在拜特兰德，他们有一个非常奇怪的货币体系。
每枚拜占庭金币上都写着一个整数。一枚硬币可以在银行里兑换成三个硬币：n/2、n/3和n/4。但这些数字都是四舍五入的(银行必须盈利)。
你也可以以美元出售拜占庭硬币。汇率是1:1，但你不能买拜占庭硬币。
你有一枚金币。你能得到多少美元？
以下是我的
浏览 3提问于2014-12-27得票数 1
回答已采纳
1回答
这个问题是专门针对硬币兑换问题而提出的。我知道找到最佳硬币数量的算法，并且我也理解它，但我不理解的是，如果你愿意找到这样的解决方案，我如何“标记”所采取的路径。我尝试过使用父指针，我确信这是一种方法，但我只是不知道如何实现它。下面是一个例子。示例:给定硬币面额: 1，10，25变化: 30最佳解决方案要求:使用3枚硬币: 10，10，10
我并不擅长解决动态编程问题。
浏览 1提问于2013-05-09得票数 1
我们知道私钥对吧？
如果我们持有私钥，我们应该能够发送ETH从公共地址，然后钱被发送到我们的帐户。
我想买视频硬币。最低购买量为10 ETH。
我不想失败。
我只想确保一切都恢复正常
有人做过吗？
对于那些想要刷新记忆的人来说，问题是: ICO的工作方式是从ethereum地址寄钱，然后把钱送到同一个地址。我相信这只适用于EC20硬币。我不知道视频卡是否是一枚EC20硬币。
一般情况下，您不能使用您的兑换钱包到ICO。那是因为你的兑换钱包是托管人钱包。
但是，如果您控制公钥的私钥，则应该可以。
我的印象是，以太三角洲是好的。我不需要钱包。我只需要以太三角洲。
浏览 0提问于2018-05-08得票数 0
1回答
我有以下问题：
给定目标尺寸N和一些随机生成的硬币在阵列denominations[]中存储的面额，如果存在一个最优解，用最少的硬币填充整个目标，则使用动态规划进行检查。
这是硬币兑换问题的一个典型例子，然而，与现实生活中的货币不同的是，每一种面额都是精心挑选的，以便任何目标都能匹配--事实并非如此。
我熟悉硬币换币问题的算法，以及如何构造一个动态规划数组来寻找解，但首先如何检查是否有解？
浏览 3提问于2015-06-16得票数 0
回答已采纳
def coins(cents):
penny = cents // 25
quarter = cents // 25
dime = (cents % 25) // 10
nickel = cents % 25 % 10 // 5
print("Number of Cents:"), cents
print("Pennies:"), penny
print("Nickels:"), nickel
print("Dimes:"), dime
print(
浏览 3提问于2022-09-18得票数 0
2回答
我正在研究LeetCode 322:硬币兑换。
给您一个表示不同面值的硬币的整数数组硬币和一个代表总金额的整数数量。
归还最少数量的硬币，你需要弥补这个数额。如果这个数额的钱不能由任何组合的硬币，回报-1。
你可以假设你有无限数量的每一种硬币。
示例：
投入:硬币= 1,2,5，金额= 11
产出:3
说明: 11 =5+5+1
我选择一种自上而下的方法，在每一次迭代中，我选择一个面额不大于剩余金额的硬币。听起来很简单，对吧？
以下代码通过所有测试用例。
import sys
import functools
class Solution:
def coinChange(self,
浏览 2提问于2021-09-27得票数 0
回答已采纳
1回答
DP硬币变化解释
、、
硬币兑换是一个很流行的问题，它问你用硬币(C，C1.CK-1)可以得到多少个N美分的总和。DP解采用s(N，K) = s(N，K-1) + s(N-CK-1，K)的方法，其中s(N，K)是用第一K硬币(按升序排列)求和N的方法的数量。它意味着用第一个K硬币来制造N美分的方法的数量是不使用Kth硬币的方式达到相同金额的方法的总和，再加上计算N的方法的数量-- Kth硬币。我真的不明白你怎么能找到这个解决方案，以及它如何在逻辑上有意义。有人能解释一下吗？
浏览 6提问于2014-07-16得票数 3
回答已采纳
1回答
我有贪婪的算法，它解决了硬币兑换问题的所有可能的解决方案。硬币的最大数量是3.最少1.例如
用硬币{1,2,3,4}，我想做10和，所以程序输出
(4+4+2)
(3+3+4)
对于硬币{4，5，8，3}和和12
(3+4+5)
(4+4+4)
(4+8)
等。
问题是我的算法效率很低，因为它涉及很多循环。我搜索了很多，但只找到了算法，这些算法只显示了无数硬币的解或硬币的变化。
我的职责。硬币以前是按升序排列的。
void Count (int coins[], int cash, int n) {
int or = 3; // Be
浏览 3提问于2016-12-03得票数 1
回答已采纳
2回答
mit中的迭代“计数变化”实现
、、、、
下面是我在SICP中迭代实现的计数变化示例。请注意，我是个初学者，这意味着我目前只知道基本的语法。
要求：
我们能用多少种不同的方式来兑换1美元，半美元，25美分，一角硬币，五分硬币和便士？更广泛地说，我们是否可以编写一个程序来计算改变任何给定金额的方法的数量？
代码：
(define (count-change-iterative amount)
;; penny is not in the signiture, bacause it equals (- amount
;; (*
浏览 0提问于2016-11-19得票数 0
9回答
尝试为一般的硬币兑换问题编写DP解决方案，同时跟踪使用了哪些硬币。到目前为止，我已经让它给了我所需的最小硬币数量，但不知道如何获得使用了哪些硬币以及使用了多少次。如果使用硬币，我尝试使用值设置另一个表(布尔值)，但似乎不能正常工作。有什么想法吗？
public static int minChange(int[] denom, int changeAmount)
{
int m = denom.length;
int n = changeAmount + 1;
int[][] table = new int[m][n];
boolean[][] use
浏览 6提问于2013-11-25得票数 8
1回答
渐近运行时间分析--硬币更换算法
、、、、
我需要帮助找到以下算法的渐近运行时，即Big O(n) --> change_slow()。我尝试过masters方法和其他技术，但似乎找不到答案。
这是一个硬币兑换问题，使用以下数据范围进行处理：
for i in range(50, 950, 50):
data.append(([1,10,25,50],i))
for i in range(50, 600, 50):
data.append(([1,3,4,17,31],i))
下面是算法：
coins = item[0]
amount = item[1]
coins_needed = [j for j in
浏览 4提问于2015-02-15得票数 0
硬币换币问题已经有了很好的文档。如果有无限数量的面额硬币( x_1到x_m )，您需要找到组合的数量，这些组合加起来等于y。例如，给定x = {1,2,3}和y = 4，我们有四个组合：
{1,1,1,1}
{1,1,2}
{1,3}
{2,2}
Introduction
硬币兑换问题有几种变化。在这种变化中，我们有两个额外的限制：
每个面额必须至少使用一次。
确切地说，一定数量的硬币必须全部使用。
例如，给定x = {1,2,3}、y = 36和n = 15，其中n是必须使用的硬币总数，我们得到四个组合：
{1,2,2,2,2,2,2,2,3,3,3,3,3,3,3} (1 1，7 2，7
浏览 0提问于2016-07-29得票数 13
回答已采纳
1回答
我试着用记忆来解决“计数变化”的问题。
考虑了以下问题:给出半美元、四分之一、一角硬币、五分币和便士，我们能用多少种不同的方式来兑换1美元？更广泛地说，我们是否可以编写一个函数来计算使用任何一套货币面额来改变任何给定金额的方法的数量？
和递归的直观解决方案。
使用n种硬币改变金额的方法的数量等于
改变一种使用的硬币的方法的数量，除了第一种硬币，再加上，用所有n种硬币改变较小数量的a-d的方法的数目，其中d是第一种硬币的面值。
#+BEGIN_SRC python :results output
# cache = {} # add cache
def count_change(a, ki
浏览 0提问于2019-10-27得票数 2
回答已采纳
我正在尝试使用递归来输出N次抛硬币的可能结果。例如，如果我抛硬币3次，可能的输出可能是TTT，TTH，THT，THH，HTT，HTH，HHT和HHH。我不是在寻找答案，而是在向正确的方向推进。使用字符数组完成此操作是否最好？或者赋值H和T整数值？
浏览 0提问于2017-03-28得票数 1
4回答
我花了一段时间研究以下算法：
你会得到不同面额的硬币和总金额。编写一个函数来计算弥补这个数量所需的最少硬币数。如果这个数额的钱不能由任何组合的硬币，回报-1。
例1:硬币= 1，2，5，金额= 11回报3 (11 =5+5+ 1)
例2:硬币= 2，金额=3回报-1。
注:你可以假设你有无限数量的每种硬币。
这可能不是解决问题的最有效的方法，但我想我可以通过尝试每一个硬币并在每次尝试中启动一个新函数来解决它，其中新的函数调用具有更新的数量。每枚硬币会发出N个函数呼叫..。但我以后会处理的。
现在我正在处理以下问题:通常在进行递归调用时，我无法在基本情况下正确编码。例如，在这个问题上，我
浏览 11提问于2017-03-10得票数 1
回答已采纳
1回答
java中的算法- Coin更改
、、、、
我已经看到了相当多的硬币兑换问题，这一个是相当独特的。我试着使用DP和递归，但是我不能解决它。
这就是问题：
假设有一个价格，X，其中X是美分，我有5个有限面额的硬币，1,5,10,20,50。我有不同数量的1，5，10，20，50美分硬币。我想用最大数量的硬币来定价X。我该怎么做呢？(假设X总是可以用手头的硬币做的)
例如，如果价格X= 52，并且
我有3枚1美分的硬币
我有4枚5美分的硬币
我有8枚10美分的硬币
我有6枚20美分的硬币
我有4枚50美分的硬币
我想要找到硬币的最大数量和可以用来实现这个价格的方法的数量，在这种情况下:两个1美分，4个5美分，3个10美分的硬币将是答案。
我
浏览 1提问于2017-11-02得票数 0
2回答
据我所知，几乎所有依赖类型的语言都使用弱头范式来实现可兑换。为什么会这样呢？为什么检查可兑换性就足够了(对我来说似乎还不够)？你有什么好推荐的吗？
浏览 1提问于2014-03-24得票数 2
回答已采纳
1回答
我知道如何在硬币变化问题(从给定的一套硬币中获得一个和S的方法总数)中使用递归关系，但是我不知道它是从哪里来的。我在互联网上搜索了它，据我所知，他们提出了这个事实(重复使用r/ship)，然后继续执行它。有人能解释一下吗？
10{1,2,3,4} = 10{1,2,3} + 6{1,2,3,4}
上面的方程式只是一个例子。也就是说，用硬币{1,2,3,4}制造10的方法总数等于用{1,2,3}脉冲制作10的方法总数，用这些硬币制造6的方法总数等于{1，2，3，4}。
浏览 0提问于2020-06-20得票数 1
回答已采纳
2回答
我想把我的硬币兑换功能转换成回忆录功能。
为了做到这一点，我决定使用字典，这样我的字典中的一个键将是硬币，而价值将是一个包含所有可以改变“关键”硬币的硬币的列表。
我所做的是：
def change(a,kinds=(50,20,10,5,1)):
if(a==0):
return 1
if(a<0 or len(kinds)==0):
return 0
return change(a-kinds[0],kinds)+change(a,kinds[1:])
def memoizeChange(f):
c
浏览 0提问于2013-12-23得票数 3
回答已采纳
我遇到了两个动态规划问题。其中一个问题是
假设我一次可以跳1、2或3步，用n步爬楼梯的可能方法有多少。
解决这个问题的动态规划方法如下。
If C(n) is number of ways of climbing the staircase, then
C(n) = C(n-1) + C(n-2) + C(n-3) .
This is because , if we reach n-1 stairs, we can hop to n by 1 step hop or
if we reach n-2 stairs, we can hop to n by 2
浏览 4提问于2014-01-02得票数 7
回答已采纳
正如我在所发现的，
硬币变更是利用给定的一组面额( d_1....d_m )来找出对某一特定数量的0.分( n )进行变更的方法数的问题，它是整数划分的一般情况，可以用动态规划来解决。
这个问题通常被问到:如果我们想改变N美分，并且我们有无限供应的S={ S_1，S_2，……，S_m }值的硬币，我们能用多少种方法来改变？(为了简单起见，顺序不重要)。
我试过了，这个很好。所以我如何修改这个来找到所有可能的硬币组合，当不同硬币的顺序真的很重要的时候，。
即:以前
例如，对于N= 4，S= {1,2,3}，有四个解：{1，1，1}，{1,1,2}，{2,2}，{1,3}。
现在：
对于N= 4，
浏览 6提问于2014-09-10得票数 3
回答已采纳
我正在努力解决最低限度的硬币兑换问题。问题是:给定一个值V，如果我们想改变V美分，并且我们有无限供应的C={ C1，C2，..。有价值的硬币，要改变的硬币的最小数量是多少？
我建议的算法是：
从数组arr1 1.V开始，其中V是值：
对于所有的面额，初始化arrd=1，因为这是基本情况。如果一枚硬币的价值为==，则只需要一枚硬币，因此它是最少的。
对于I:1.V中的所有值，计算出改变'i‘值所需的硬币的最小no。2.1。这可以通过:对于所有j: 1.(i-1) arri=min(arri，arrj+arri-j)实现；
返回arrV；
这种逻辑是有缺陷的，还是涵盖了
浏览 1提问于2019-06-30得票数 2
回答已采纳
2回答
我们正在做一个经典的问题，确定我们可以做出改变的方式的数量，这相当于Z，给定了一套硬币。
例如，Amount=5和Coins={1，2，3}。我们可以制造5的一种方法是{2，3}。
朴素递归解具有阶乘时间的时间复杂性。
f(n) =n* f(n-1) = n！
我的教授认为它实际上具有O(2^n)的时间复杂性，因为我们只选择使用硬币或不使用硬币。这从直觉上讲是有道理的。然而，为什么我的递归不是O(2^n)
编辑：
我的复发率如下：
f(5, {1, 2, 3})
/ \ .....
f(4, {2, 3})
浏览 5提问于2016-04-03得票数 1
1回答
我正在尝试返回所有可能的独特的‘管道’的组合，需要至少覆盖提供的英尺数量。
这个问题类似于常见的硬币兑换算法。
管道的增量为10‘、25’和50‘。
我已经看过来自和的示例，它们看起来很接近，但是，我想返回所有可能的组合，而不是简单地计算它们。
这是我当前的代码：
let allCombos = [];
let pipeAmounts = [50, 25, 10];
function findPiping (feet, index, combo) {
if (index > pipeAmounts-1) {
return;
}
let ma
浏览 6提问于2017-12-30得票数 1
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
