概述
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11输出: 3
解释: 11 = 5 + 5 + 1示例 2:
输入: coins = [2], amount = 3
输出: -1说明:
你可以认为每种硬币的数量是无限的。
1.自顶向下+备忘录：
class 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.自底向上的方法：
class 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
---------------------
#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的所有数值
#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;
}
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
方法一：暴力递归
int 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/ 此题
int 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;
}
方法二：带记录表的暴力
int 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有多少种方法
int 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];
}
还有一种写法：
class 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];
}
}
最后
以上就是优雅抽屉为你收集整理的【题目记录】动态规划找零钱的全部内容，希望文章能够帮你解决【题目记录】动态规划找零钱所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复