有2元的 5元的 7元的 硬币若干，凑出27元，需要最小硬币数
这是一个动态规划问题，对动态规划求解的思路如下：
1.确定状态：确定最后一步和倒数第二步之间的关系，就是把后面的问题转化为前面的子问题
x可以由x-2的情况再选面值2的硬币得到，也可以由x-5的情况选5面值的得到，还可以由x-7由面值7的得到
2.根据状态写出转移方程
dp[i]=min(dp[i-2]+1,dp[i-5]+1,dp[i-7]+1,dp[i]);
3.确定初始条件和边界情况
初始条件dp[0]=0
数组不能越界，考虑i-2和i-5和i-7的越界情况
#include<iostream> #include<string.h> #include<math.h> using namespace std; int n,m,k; int ans; int mod=1e9+7; int a[105]; bool vis[105]; int main(){ cin>>n; memset(a,999999,sizeof(a)); a[0]=0; for(int i=1;i<=n;i++){ if(i>=2){ a[i]=min(a[i],a[i-2]+1); } if(i>=5){ a[i]=min(a[i],a[i-5]+1); } if(i>=7){ a[i]=min(a[i],a[i-7]+1); } } cout<<a[n]; return 0; }
更一般的，告诉m种硬币的值每种值bi，求凑够n需要最小硬币数
#include<iostream> #include<string.h> #include<math.h> using namespace std; int n,m,k; int ans; int mod=1e9+7; int dp[105],b[105]; bool vis[105]; int main(){ cin>>n>>m; // n:换的总钱价值 m:硬币总数 for(int i=0;i<m;i++){ cin>>b[i]; // 每种硬币的价值 } memset(dp,999999,sizeof(dp)); //初始化设置dp较大值 便于后面更新 dp[0]=0; //初始条件 dp[0]=0 for(int i=1;i<=n;i++){ //到 i 需要换的硬币最小个数 for(int j=0;j<m;j++){ //依此考虑到 i 后每种硬币可能的换的最小个数 if(i>=b[j]){ dp[i]=min(dp[i],dp[i-b[j]]+1); } } } cout<<dp[n]; return 0; }
原文：https://www.cnblogs.com/xusi/p/12490020.html