题目描述： 给出一些面额硬币，求构成N的最少硬币数量。
如2,3,5 3枚硬币，求给出N=11的最少硬币数量。
如果用贪心算法，那么有一定几率可以正确，但是有时候会有例外： 比如贪心是一直取最大，那么就会发现取不到11组成，但是的确存在—-3+3+5或3+3+3+2取最少，为3.
dp[i] = min{dp[i-a1]+1,dp[i-a2]+1……}. 这里a1,a2是可以使用的硬币面值
代码：
#include<stdio.h> int dp[100000+10]; int main(){ int num,N,coin[10],mins=0x7fffffff; scanf("%d",&num); for(int i = 0;i<num;i++){ scanf("%d",&coin[i]); mins = coin[i]>mins?mins:coin[i]; } scanf("%d",&N); printf("%d\n",mins); for(int i = mins ;i<=N;i++){ int min = 0x7fffffff; for(int j = 0;j<num;j++){ if(i-coin[j]>=0){ if(i==coin[j]){min=1;break;}//如果刚好等于面值，那么这肯定是最佳的 if(dp[i-coin[j]]>0)min = dp[i-coin[j]]+1<min?dp[i-coin[j]]+1:min;//i-coin[j]表示，我先选中coin[j]面值，那么之前的方法数dp[i-coin[j]]再加上选中的coin[j]的方法数为1,即dp[i-coin[j]]+1 } } dp[i] = min==0x7fffffff?0:min; } for(int i = 2;i<=N;i++){ printf("%d ",dp[i]); } return 0; }