硬币兑换问题的递归解法
硬币兑换问题是一个经典的动态规划问题，它的目标是找到一种最优的方式来用最少的硬币数量兑换给定的金额。
递归解法是一种常见的解决动态规划问题的方法。在硬币兑换问题中，可以使用递归函数来实现。
首先，我们需要定义一个递归函数，该函数接受两个参数：要兑换的金额和可用的硬币面额。函数的返回值是兑换给定金额所需的最少硬币数量。
递归函数的基本思路是：
- 如果金额为0，表示已经完成兑换，返回0。
- 如果金额小于0，表示无法完成兑换，返回一个较大的值，比如无穷大。
- 对于每个硬币面额，递归调用函数，计算使用该硬币和剩余金额进行兑换所需的最少硬币数量。
- 返回所有硬币面额中最小的兑换数量。
以下是一个示例的递归解法的代码：
def coinChange(amount, coins):
# 递归终止条件
if amount == 0:
return 0
if amount < 0:
return float('inf')
# 初始化最小兑换数量为无穷大
min_coins = float('inf')
# 遍历每个硬币面额
for coin in coins:
# 递归调用函数，计算使用该硬币和剩余金额进行兑换所需的最少硬币数量
res = coinChange(amount - coin, coins)
# 更新最小兑换数量
min_coins = min(min_coins, res + 1)
return min_coins然而，递归解法在面对大规模的硬币兑换问题时效率较低，因为它会重复计算许多相同的子问题。为了提高效率，可以使用动态规划的方法来解决硬币兑换问题。
动态规划解法的思路是：
- 创建一个数组dp，其中dp[i]表示兑换金额i所需的最少硬币数量。
- 初始化dp数组，将所有元素的值设置为无穷大。
- 将dp[0]设置为0，表示兑换金额为0时不需要任何硬币。
- 遍历金额从1到目标金额的所有可能取值，对于每个金额i，计算使用每个硬币面额进行兑换所需的最少硬币数量，并更新dp[i]的值。
- 返回dp[amount]作为最终的结果。
以下是一个示例的动态规划解法的代码：
def coinChange(amount, coins):
# 创建dp数组
dp = [float('inf')] * (amount + 1)
# 初始化dp数组
dp[0] = 0
# 遍历金额从1到目标金额的所有可能取值
for i in range(1, amount + 1):
# 遍历每个硬币面额
for coin in coins:
# 如果当前硬币面额小于等于当前金额
if coin <= i:
# 更新dp[i]的值
dp[i] = min(dp[i], dp[i - coin] + 1)
# 返回最终结果
return dp[amount]以上是硬币兑换问题的递归解法和动态规划解法。递归解法简单直观，但效率较低；动态规划解法通过保存中间结果，避免了重复计算，提高了效率。在实际应用中，建议使用动态规划解法来解决硬币兑换问题。
腾讯云相关产品和产品介绍链接地址：
- 云计算：https://cloud.tencent.com/product
- 云原生：https://cloud.tencent.com/solution/cloud-native
- 数据库：https://cloud.tencent.com/product/cdb
- 服务器运维：https://cloud.tencent.com/product/cvm
- 网络通信：https://cloud.tencent.com/product/vpc
- 网络安全：https://cloud.tencent.com/product/ddos
- 音视频：https://cloud.tencent.com/product/vod
- 多媒体处理：https://cloud.tencent.com/product/mps
- 人工智能：https://cloud.tencent.com/product/ai
- 物联网：https://cloud.tencent.com/product/iotexplorer
- 移动开发：https://cloud.tencent.com/product/mobapp
- 存储：https://cloud.tencent.com/product/cos
- 区块链：https://cloud.tencent.com/product/baas
- 元宇宙：https://cloud.tencent.com/solution/metaverse
请注意，以上链接仅供参考，具体产品选择应根据实际需求进行评估和决策。
相关·内容
我已经实现了货币兑换问题，例如，用尽可能少的硬币兑换一定数量的货币。可用的面值有: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
2回答
我在练习动态编程。我的重点是硬币兑换问题的以下变体：
设S = [1, 2, 6, 12, 24, 48, 60]是一组整数的硬币面额。让n是一个正整数金额的钱可以通过硬币在S。考虑两个人A和B。我可以用多少种不同的方式将n分割成A和B，这样每个人都能得到相同数量的硬币(不考虑每个人实际得到的钱币数量)？
示例
n = 6可以分为4种不同的方式：
Person A获取{2，2}，person B获取{1，1}。
Person A获取{2，1}，person B获取{2，1}。
Person A获取{1，1}，person B获取{2，2}。
Person A获得{1，1，1}，
浏览 0提问于2018-05-06得票数 3
回答已采纳
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
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
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回答
我有一个低效的递归硬币兑换函数，它计算出给定数量的硬币组合的数量。如果可能的话，我想把它转换成一个更有效的迭代函数。
一个问题是，我正在使用回溯在一个称为面额的数组中尝试不同的硬币。我也在使用memoization，但当数量很大时，它不会加快速度。
下面是我的代码：
unsigned long long CalculateCombinations(std::vector<double> &denominations, std::vector<double> change,
double amount, unsigned int index)
{
浏览 2提问于2018-06-21得票数 0
有很多硬币兑换的问题和答案，但我找不到这个，我想知道这是否甚至是一个硬币兑换问题。
基本上，我有一堆不同的硬币，每个硬币的数量都是无限的。
所以说，这里有各种各样的教派。每个堆栈都是无限的。( 25c硬币的数目是无限的，2c硬币的数目是无限的)。
然而，在每一叠硬币的顶部是一个特殊的硬币，其价值大于(或等于)以下硬币。如果不使用上面的硬币，我就无法进入下面的硬币。
我想找出的是一定数量的硬币的最低数量。
我认为这是可解决的动态规划，但我不知道如何在传统的解决方案中添加这个限制。
我在想，一旦我使用了特殊的硬币，用普通的硬币来代替它，我是否应该删除它，但我似乎无法推理，这是否会破坏算法。
浏览 6提问于2015-10-24得票数 1
回答已采纳
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
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
回答已采纳
1回答
我知道如何使用命令式编程和DP解决硬币更改问题。
我知道如何用FP和非尾递归来解决硬币变化问题。但是它会多次计算相同的问题，从而导致效率低下。
我知道如何用FP和DP/tail递归来计算斐波纳契数。许多文章使用这个例子来解释"FP可以与DP“”和“结合起来，递归也可以和循环”“一样高效。
但是我不知道如何用FP和DP/tail递归来解决硬币变化问题。
我认为奇怪的是，关于命令式编程的文章总是多次提到计算相同问题的效率低下的问题，而FP上的文章则忽略了这一点。
在更一般的意义上，我想知道FP是否足够强大来解决这样的“二维”问题，而fibonacci是一个“一维”问题。有人能帮我吗？
硬币
浏览 1提问于2015-04-26得票数 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回答
我是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, 15, 25}和总和30，贪婪算法首先选择25，剩余5，然后选择五个1，总共六个硬币。但硬币数量最少的解决方案是选择15两次。
一组硬币必须满足什么条件才能使贪婪算法找到所有和的最小解？
浏览 7提问于2012-11-26得票数 84
1回答
这个问题是专门针对硬币兑换问题而提出的。我知道找到最佳硬币数量的算法，并且我也理解它，但我不理解的是，如果你愿意找到这样的解决方案，我如何“标记”所采取的路径。我尝试过使用父指针，我确信这是一种方法，但我只是不知道如何实现它。下面是一个例子。示例:给定硬币面额: 1，10，25变化: 30最佳解决方案要求:使用3枚硬币: 10，10，10
我并不擅长解决动态编程问题。
浏览 1提问于2013-05-09得票数 1
3回答
我已经在网站上查看过各种问题，也没有找到通过以下推理实现这一点的任何东西(所以我希望这不是一个副本)。
我试图通过C程序解决的问题如下：
作为自动售货机控制器的程序员，您需要计算组成所需更改的硬币的最小数量，以回馈客户。解决这一问题的有效方法是采用动态规划方法，首先计算1美分兑换所需的硬币数量，然后再计算2美分，然后再计算3美分，直到达到所需的变化为止，每次都使用先前计算的硬币数量。编写一个包含函数ComputeChange()的程序，其中包含有效硬币和所需更改的列表。此程序应从控制台反复请求所需的更改，并相应地调用ComputeChange()。它还应该使用“缓存”，其中任何先前计算过的中
浏览 8提问于2016-02-03得票数 15
回答已采纳
我对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
我们知道私钥对吧？
如果我们持有私钥，我们应该能够发送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回答
渐近运行时间分析--硬币更换算法
、、、、
我需要帮助找到以下算法的渐近运行时，即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
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
回答已采纳
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回答
我想把我的硬币兑换功能转换成回忆录功能。
为了做到这一点，我决定使用字典，这样我的字典中的一个键将是硬币，而价值将是一个包含所有可以改变“关键”硬币的硬币的列表。
我所做的是：
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
回答已采纳
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
回答已采纳
我正在努力解决最低限度的硬币兑换问题。问题是:给定一个值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
回答已采纳
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
回答已采纳
例如，如果我们有以下问题：
给出一套硬币- 1,2,5和一笔- 11.找到制造11枚硬币所需的最低数量。
我们可以使用递归来探索状态空间。例如，根是空的，我们从硬币数组的索引0开始。从根本上说，我们可以选择取硬币1(硬币阵列指数0)，也可以不取硬币1，继续递归地探索状态空间。
但是我们如何选择用于回忆录的变量呢？是否有任何定义的通用方式来选择它？
在这个问题上，凭直觉，我选择了以下变量用于回忆录：
元组键：(硬币和，我们正在探索的硬币数组索引)值:硬币的数
但不起作用。
浏览 1提问于2021-03-28得票数 0
如果矿工处理未更新到Muir Glacier的事务会发生什么？我会不会因为矿工还在旧的链子上而把硬币弄松了，那么硬币现在就在冰河上了吗？
我很担心，因为我在分叉后的几个街区(大约9'200'010)将硬币从兑换处寄到我的钱包。也许这还为时尚早，因为当时一些矿工或基础设施提供商没有得到更新。据"https://ethernodes.org/muir_冰川“称，仍有许多矿工尚未证实这一最新消息。
因此，一般说来:有人在紧挨着硬叉块高度做交易时，会不会把硬币弄松？
浏览 0提问于2020-01-26得票数 0
0/1 knapsack的概念-使用给定的weights.Aim填充一个W重量的背包是为了最大化利润。Ans问题可以通过采用特定的权重或不采用特定的权重来解决，这取决于哪一个给出了最大的profit.In，这样就可以计算出最优解。
现在，最小硬币兑换问题-找到最小否。来做一个特殊的改变。答案-根据我的想法，它可以通过拿一枚特定的硬币或不拿一枚硬币来解决，这取决于哪一枚给的是最小的否。硬币的数量。只有0/1背包中的最大值条件才会被颠倒。
但在实际解决方案中是这样的-
现在，最小硬币变化问题-我们必须找到的所有可能的硬币组合对于特定的变化，背包的概念随之而来。我不明白为什么？？
请帮助我理解为
浏览 0提问于2015-10-13得票数 3
1回答
伙计们，出于某种原因，我的贪得无厌的硬币兑换计划行不通。函数应该返回最小数量的硬币，您可以更改一个值，还有一个数组，其中包括您可以用于此的硬币。我的程序没有显示任何东西，我不知道为什么。
public class Main {
public static int coinChangeGreedy(int[] coins, int n) {
int result = 0;
while (n != 0)
{
for (int i=coins.length - 1 ; i>=0 ; i--)
浏览 2提问于2017-10-15得票数 0
回答已采纳
我现在正在研究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
回答已采纳
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
2回答
我想把美元寄到另一个钱包或兑换处。我试图发送到Binance地址(我有与Coinbase地址相同的错误)，但是我收到了这个错误:事务可能需要0.00038 BNB (0,17美元)。请多存一些ETH。在我的硬币钱包，我有133美元的ETH，那么问题是什么？我不明白。你能帮帮我吗？
📷
📷
谢谢
浏览 0提问于2022-01-19得票数 0
我有一个暴力解决方案与回溯来解决硬币兑换问题。目前，我得到了可以使用的最小硬币数量。但我怎样才能退还实际使用过的硬币呢？例如，如果金额是100，那么我想返回25，25，25，25。
我当前的代码如下：
public class Solution {
public static void main(String[] args) {
Solution s = new Solution();
int coinChange = s.coinChange(0, new int[] { 1, 25, 50 }, 100);
System.out.println(coinChan
浏览 8提问于2018-11-28得票数 2
1回答
我昨天从硬币兑换处寄了一些ETH到我的ETH钱包。煤气限值为21000，用气量为21000，煤气价格为111.608。所收取的费用大约是。0.00234 ETH，大约。8%的ETH转移(我发送了很小的数量)。我是ETH的新手，对汽油价格等做了一些基本的了解，但似乎我可以以同样的费用转移一枚ETH硬币。我说的对吗？如果是这样的话，那么在转移之前，应该总是积累至少一个ETH才能将费用降到最低？
谢谢。
浏览 0提问于2021-08-31得票数 0
回答已采纳
2回答
我目前正在研究leetcode上的硬币兑换动态编程问题-- https://leetcode.com/problems/coin-change/。 下面是问题陈述： You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made u
浏览 14提问于2019-03-05得票数 4
回答已采纳
我很难理解臭名昭著的"用n个掷骰子的k面找出达到给定和的总方法“问题背后的逻辑。在广泛寻找解释之后，我出现了空白。
我的困惑源于这样一个事实，即它似乎不遵循“用硬币进行改变的方法的数量”问题的逻辑，这一点在许多视频中得到了很好的解释，尤其是这 one。
我对硬币兑换问题的理解
我相信这是相当合理的。从本质上说，当我们越过第一排时，我们会从第一枚硬币和第二枚硬币，而不仅仅是第二枚硬币(一般来说，它是当前硬币加上所有以前的硬币)，来确定目标的数量。正如在链接视频中所解释的，我们需要遵循一些规则才能做到这一点：
If <the value of the coin is greater
浏览 0提问于2019-08-21得票数 4
回答已采纳
我试图用动态规划来解决一个问题，问题如下：
如果硬币(硬币、镍币、一角硬币、双一角硬币、四分之一硬币)的价值(1、5、10、20、25)是无限供应的，请找出最小数量的硬币来兑换65美分。使用了什么硬币(每个硬币多少枚)？说明使用动态规划算法所需的表格，以及如何获得所使用的硬币。
注:我不希望任何人为我演示整个表，但我有点拘泥于如何填写这个问题的表格。
我知道我的桌子看起来有点像这样：
5 10 15 20 25 30 35 40 45 50 55 60 65
1
5
10
20
25
(我忽略了1，因为我知道这不是最好的解决方案)我最初的想法是，这张桌
浏览 1提问于2014-10-29得票数 1
回答已采纳
1回答
我在网上看到的问题:一个卖瓜的农民有n个瓜。每个甜瓜的重量，一个整数(磅)，是不同的。一位顾客要了整整一百万磅未切好的西瓜。现在，农夫有以下问题:如果有可能满足客户，他应该通过尽可能有效地找到合适的瓜来做到这一点，否则就告诉客户不可能满足他的要求。
注意:这不是家庭作业，顺便说一下，我只是需要指导。
我的回答是:这似乎类似于硬币兑换问题(背包)和子集问题(回溯)。硬币更换:我可以将权重放入一个集合w= {5，8，3，2，...}，然后求解，子集问题也是如此。
所以基本上我可以使用任何一种方法来解决这个问题？
浏览 0提问于2013-07-17得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
