给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
复制代码
1
2
3输入: coins = [1, 2, 5], amount = 11输出: 3 解释: 11 = 5 + 5 + 1
示例 2:
复制代码
1
2
3输入: coins = [2], amount = 3 输出: -1
说明:
你可以认为每种硬币的数量是无限的。
1.自顶向下+备忘录：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution { public: int coinChange(vector<int>& coins, int amount) { if(amount < 1) return 0; vector<int> res(amount+1,0); return dp(coins,amount,res); } int dp(vector<int>& coins, int amount,vector<int>& res){ int q=INT_MAX; if(amount == 0) return 0; if(res[amount] != 0) return res[amount]; if(amount < 0) return -1; else{ for(int i=0;i<coins.size();i++){ int tmp=dp(coins,amount-coins[i],res); if(tmp>=0 && tmp<q) q=tmp+1; } } res[amount] = q==INT_MAX ? -1 : q; return res[amount]; } };
2.自底向上的方法：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution { public: int coinChange(vector<int>& coins, int amount) { int Max = amount +1; vector<int> dp(amount + 1, Max); dp[0]=0; for(int i=1;i<=amount;i++) //从下到上，即从1元找零开始，推到题目给的amount for(int j=0;j<coins.size();j++) //对每个钱数找零情况，都从最小的零钱开始找，逐步更新零钱面额增大的最小找钱情况 if(coins[j]<=i) dp[i]=min(dp[i],dp[i-coins[j]]+1); //min中dp[i]的更新条件是用了1个此面额找完钱后，剩下的amount需要零钱个数+1会小于不用此面额找钱的个数（不用此面额找钱的个数初始设为最大） return dp[amount] > amount ? -1 : dp[amount]; //dp[amount] > amount 是初始为真的 } }
3.各面额零钱个数有限的情况
作者：2017gdgzoi999
原文：https://blog.csdn.net/drtlstf/article/details/80258580
用dfs
Description
有1元、5元、10元、50元、100元、500元的硬币各c1、c5、c10、c50、c100、c500枚。现在要用这些硬币来支付A元，最少需要多少枚硬币？假定本题至少存在一种支付方案。
Input
一行c1、c5、c10、c50、c100、c500、A，中间用空格隔开。
Output
最少的硬币数量。
Sample Input
3 2 1 3 0 2 620
Sample Output
6
HINT
【注释】
500元硬币1枚，50元硬币2枚，10元硬币1枚，5元硬币2枚，合计6枚。
【限制条件】
0<= c1、c5、c10、c50、c100、c500<=10^9
0<=A<=10^9
---------------------
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37#include <iostream> #define SIZE 501 using namespace std; int a[SIZE], c[6] = {500, 100, 50, 10, 5, 1}; int dfs(int l, int k) // 深度优先搜索 { int i; if (!l) { return k; } for (i = 0; i < 6; i++) { if ((l >= c[i]) && (a[c[i]])) { a[c[i]]--; // 数量-1 return dfs(l - c[i], k + 1); // 继续搜索 } } } int main(int argc, char** argv) { int l; cin >> a[1] >> a[5] >> a[10] >> a[50] >> a[100] >> a[500] >> l; // 读入数据 cout << dfs(l, 0) << endl; return 0; }
腾讯2019.4.5笔试第一题，给定零钱面额的数组，带最少的零钱个数能凑出1~m的所有数值
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<vector> #include<algorithm> using namespace std; const int N = 110; int a[N]; int n, m; int main() { cin >> m >> n; for (int i = 0; i < n; i++) cin >> a[i]; sort(a, a + n); if (a[0] != 1) puts("-1"); else { while (n > 0 && a[n - 1] > m) n--; a[n] = m + 1; //保证公式计算一致性 int res = 0; for (int i = 0, s = 0; i < n; i++) { int k = (a[i + 1] - 1 - s + a[i] - 1) / a[i]; // 公式k= a[i+1]-1-s / a[i] 向上取整 其中s是当前a[0]~a[i-1]的硬币能凑出的最大钱数 res += k; s += k * a[i]; } cout << res << endl; } system("pause"); return 0; }
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
方法一：暴力递归
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19int change(int amount, vector<int>& coins) { if(amount<0) return 0; return func(amount,coins,0); } int func(int amount, vector<int>& coins, int index){ int res=0; if (index == coins.size()){ res= amount == 0 ? 1 : 0; return res; } for(int i=0; coins[index] * i <= amount; i++){ res += func(amount - coins[index] * i , coins, index + 1); } return res; }
或https://leetcode-cn.com/problems/coin-lcci/solution/ 此题
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22int coins[4] = {25,10,5,1}; int waysToChange(int n) { int ans = 0; judge(n,coins,0,ans); return ans; } void judge(int n,int* coins, int pos, int& ans){ if(pos >= 4 || n<0) return; if(n==0){ ans++; ans%=1000000007; return; } for(int i=pos;i<4;i++){ if(n >= coins[i]){ judge(n-coins[i],coins,i,ans); } } return; }
方法二：带记录表的暴力
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26int change(int amount, vector<int>& coins) { if(amount<0) return 0; vector<vector<int> > record(coins.size()+1,vector<int>(amount+1,0)); return func(amount,coins,0,record); } int func(int amount, vector<int>& coins, int index, vector<vector<int> >&record){ int res=0; if (index == coins.size()){ res = amount == 0 ? 1 : 0; } else{ for(int i=0; coins[index] * i <= amount; i++){ int r = record[index+1][amount - coins[index] * i]; //index+1表示下一层的结果 if(r != 0){ res += r==-1? 0 : r; } else res += func(amount - coins[index] * i , coins, index + 1, record); } } record[index][amount] = res == 0 ? -1:res; return res; }
方法三：dp
如果用coins[index,..N-1]这些面值的钱组成amount,返回总的方法数
dp[i][j]表示使用coins[0,...,i]货币的情况下，组成钱数j有多少种方法
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29int change(int amount, vector<int>& coins) { if(amount<0 || (coins.size()==0 && amount!=0) ) return 0; if(coins.size()==0 && amount==0) return 1; vector<vector<int> > dp(coins.size(),vector<int>(amount+1,0)); for(int i=0;i<coins.size();i++) dp[i][0]=1; for(int i=0;i<amount+1;i++){ if(i%coins[0]==0) dp[0][i]=1; else dp[0][i]=0; } for(int i=1;i<coins.size();i++){ for(int j=1;j<amount+1;j++){ //for(int k=0;k*coins[i]<=j;k++) // dp[i][j]+=dp[i-1][j-k*coins[i]]; if(coins[i]<=j) //动态规划改进 dp[i][j]=dp[i-1][j]+dp[i][j-coins[i]]; else dp[i][j]=dp[i-1][j]; } } return dp[coins.size()-1][amount]; }
还有一种写法：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution { public int change(int amount, int[] coins) { int dp[] = new int[amount+1]; // 设置起始状态 dp[0] = 1; for (int coin : coins) { // 记录每添加一种面额的零钱，总金额j的变化 for (int j = 1; j <= amount; j++) { if (j >= coin) { // 在上一钟零钱状态的基础上增大 // 例如对于总额5，当只有面额为1的零钱时，只有一种可能 5x1 // 当加了面额为2的零钱时，除了原来的那一种可能外 // 还加上了组合了两块钱的情况，而总额为5是在总额为3的基础上加上两块钱来的 // 所以就加上此时总额为3的所有组合情况 dp[j] = dp[j] + dp[j - coin]; } } } return dp[amount]; } }
最后
以上就是优雅抽屉最近收集整理的关于【题目记录】动态规划找零钱的全部内容，更多相关【题目记录】动态规划找零钱内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复