- qt - 在 QNetworkAccessManager 中,何时从解析 DNS 的 IP 列表中选择 IP?
- java - OKHTTP——发布用户输入数据,检索 JSON 响应以确定成功
- java - 将 curl 请求转换为 URLConnection
- android - 使用主机名对本地机器的 Http 请求在 android 设备中不起作用
该问题需要计算特定成本的硬币变化次数。
例如,如果我有 50, 20, 10, 5, 1
的硬币值(value),我可以形成以下成本:
5 => (5), (11111), 这是2种方式。
10 => (10), (5, 5), (5, 11111), (11111, 11111),这是4种方式。
这是我的功能。它从 10 的成本请求返回错误的结果(返回 9 种方式,而实际的方式只有 4 种)
int dp[10000];
int coins[] = { 50, 20, 10, 5, 1 };
int rec(int n)
{
if (n == 0) return 1;
if (dp[n] != -1) return dp[n];
int cnt = 0;
for (int i = 0; i < 5; i++)
if (coins[i] <= n) cnt += rec(n - coins[i]);
return dp[n] = cnt;
}
如何修复此函数以提供正确的方法数?这个算法是否正确?查看完整代码及其输出 here
注意:我的问题不在于dp
数组初始化。每次调用 rec
之前,我都使用 memset
将其初始化为 -1
。
最佳答案
(5, 1, 1, 1, 1, 1) 和 (1, 1, 1, 5, 1, 1) 在你的算法中是不同的方式,你应该保持递减。
int dp[10000][5]; // dp[20][2] means, if the biggest coin is coins[2],
// how much ways for 20 ?
int coins[] = { 1, 5, 10, 20, 50 }; // here
int rec(int n, int m)
{
int cnt = 0;
int i;
if (n == 0) return 1;
//if (m == 0) return 1;
if (dp[n][m] != -1) return dp[n][m];
for (i = 0; i <= m; i++)
if (coins[i] <= n) cnt += rec(n - coins[i], i);
return dp[n][m] = cnt;
}
int main()
{
memset(dp, -1, sizeof(dp));
printf("%d\n", rec(10, 4));
}
关于c++ - DP - 计数硬币变化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11861038/
我目前正在做一个项目,试图开发一种用于 P2P 能源交易的货币和模型,其中每产生一千瓦时的可再生能源就会向该生产商类型转换一枚硬币。我的问题是关于销毁智能合约中的代币。 所有与我的项目类似的当前实现都
在没有Maps帮助的情况下通过Memoization解决问题,由于读取文件的方法,我得到了TLE,根据我的说法,这不应该是这种情况。可能的原因是什么? 这是给出 AC - http://ideone.
考虑下面这段伪代码,其中d是面额值数组,k是面额数,n是要进行更改的金额。 Change(d; k; n) 1 C[0] 我真的不明白这部分,你为什么要用它,谁能给我解释一下! 最佳答案 为了回答
我正在尝试在我的网站上实现 Coin Slider (http://workshop.rs/2010/04/coin-slider-image-slider-with-unique-effects/)
我有使用硬币 slider 的画廊 var $jq = jQuery.noConflict(); $jq(window).load(function() { var imhei
我使用了从该站点提取的硬币 slider http://workshop.rs/projects/coin-slider/ .它现在自动滚动并仅在悬停时显示上一个和下一个。我需要禁用自动滚动并正常显示
我的问题是一道CodeFu练习题(2012 round 2 problem 3)。它基本上归结为将整数数组分成两个(几乎)相等的两半并返回两者之间可能的最小差异。我在下面包含了问题描述。如评论中所述,
我们的老师要求我们制作一 jar 硬币,用来计算我们有多少便士、一毛钱等,然后给出总金额。 这是他希望我们使用的模板 https://online.pcc.edu/content/enforced/7
我正在尝试使用币安币 future 的 api 下载 BTC/USD 永续 future 的历史价格数据,具体来说,我想使用 this endpoint .但是,我找不到必须为 BTC/USD 指定的
我上周刚开始学习计算机科学,我们得到了一个名为“硬币”的工作表,其中我必须找出一组硬币中有多少个 25 美分、10 美分、5 美分和 10 便士。我遇到了很多麻烦,并收到了该错误。这是我的代码 pac
我正在构建一些使用消耗性硬币的测验。我使用 NSUserDefault 来保存设备上的硬币及其工作。我还在 qiuz 中使用 CloudKit 处理数据。 不麻烦的是,如果用户切换设备如何恢复硬币?有
我是一名优秀的程序员,十分优秀!