硬币问题
n种硬币，面值v1，v2...vn，数量无限，输入s，使最少的硬币组合之和为s。（贪心解决的硬币问题使特殊面值，此处面对任意面值）
Min[i]是金额i对应的最少硬币数量，易得Min[i]=min(Min[i]，Min[i-1]+1)。（如果面值是1的话）
从Min[i-1]到Min[i]的递推称为状态转移。
代码如下：
#include<bits/stdc++.h> using namespace std; const int MONEY=251; const int VALUE=5; int type[VALUE]={1,5,10,25,50}; int Min[MONEY]; void solve(){ for(int k=0;k<MONEY;k++){ Min[k]=INT_MAX; } Min[0]=0; for(int j=0;j<VALUE;j++){ for(int i=type[j];i<MONEY;i++){ Min[i]=min(Min[i],Min[i-type[j]]+1); } } } int main() { int s; solve(); while(~scanf("%d",&s)){ printf("%d\n",Min[s]); } return 0; }
不行了，年轻人肾不好体谅一下，明天再来......
原文：https://www.cnblogs.com/Untergehen/p/14319571.html