硬币问题DP
题目描述
今有面值为 1、5、11 元的硬币各无限枚。
想要凑出 nn 元，问需要的最少硬币数量。
输入格式
仅一行，一个正整数 nn。
输出格式
仅一行，一个正整数，表示需要的硬币个数。
输入数据 1
15
Copy
输出数据 1
3
Copy
输入数据 2
12
Copy
输出数据 2
2
Copy
提示
样例解释
对于样例数据 1，最佳方案是 15=5+5+515=5+5+5，使用到 3 枚硬币。
对于样例数据 2，最佳方案是 12=11+112=11+1，使用到 2 枚硬币。
数据规模与约定
对于 100%100% 的数据，保证 n≤1000000n≤1000000。
代码
#include<bits/stdc++.h>
using namespace std;
int dp[1000001],n,c;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
c=0x3F3F3F3F;
if(i-1>=0)c=min(c,dp[i-1]+1);
if(i-5>=0)c=min(c,dp[i-5]+1);
if(i-11>=0)c=min(c,dp[i-11]+1);
dp[i]=c;
}
cout<<dp[n];
return 0;
}原文地址：https://blog.csdn.net/2401_87061204/article/details/143695608
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！