这篇使用动态规划算法来解决这个问题，借这篇博客初窥动态规划算法。最少钱币数问题也可以看作多重背包问题。
那么什么是动态规划算法？
动态规划(dynamic programming，DP)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。
20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。（思想也有点像分布式处理） ———From Baidupedia
那么我们如何去描述它？
动态规划算法通常基于一个递推公式及一个或多个初始状态。 当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度， 因此它比回溯法、暴力法等要快许多。 ——From 从动态规划新手到专家
概念讲完，开始做题。
————————————————
题目：
最少钱币数
【问题描述 】
这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了 6 种钱币面值为 2、5、10、20、50、100，用来凑 15 元，可以用 5 个 2 元、1个 5 元，或者 3 个 5 元，或者 1 个 5 元、1个 10 元，等等。显然，最少需要 2 个钱币才能凑成 15 元。 你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。
【输入形式】
输入可以有多个测试用例。每个测试用例的第一行是待凑的钱数值 M（1 money; if(0 == money)break; //结束标志 int dp[money+1]; //动态规划数组 dp[0] = 0; //初始化第一个元素为0，因为要凑0元需要0个钱币 cin >> kind; //硬币面值种类数 for(int k=0; k> coins[k]; //读入硬币面值，存入数组coins[] } for(int i = 1; i