最少钱币数（凑硬币）详解

目录

题目：

分析：

C++动态规划算法代码：

总结：

这篇使用动态规划算法来解决这个问题，借这篇博客初窥动态规划算法。最少钱币数问题也可以看作多重背包问题。

那么什么是动态规划算法？

动态规划(dynamic programming，DP)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。（思想也有点像分布式处理）

                                                                                                                                  ———From Baidupedia

那么我们如何去描述它？

动态规划算法通常基于一个递推公式及一个或多个初始状态。 当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度， 因此它比回溯法、暴力法等要快许多。

                                                                                                                         ——From 从动态规划新手到专家

概念讲完，开始做题。

这里可能就会有人问了，为什么还要和dp[m]比较后再存入dp[m]，正如上面的例子，因为我们在凑够m元时，可能有多种可行的方案，我们要比较出哪一种方案所需硬币数目最小。例如在4种硬币1、3、5、7元凑8元的时候会有三种方案，1）8个1元；2）3+5元；3）1+7元。我们得从中找到我们所要的答案。（如果用贪心算法的话可能会错过最优解）

有了动态转移方程，问题基本就算解决了。当然，Talk is cheap,show me the code!