动态规划之Coin Change Fewest Number（C语言，Java实现）
一、问题定义：
You given coins of different denominations and a total amount of money amount. Find the fewest number of coins that you need to make up that amount.
具体化一下：假设你有三种硬币，面值分别为1，3，5，每种硬币有足够多，现在需要11元，求最少的硬币组合
二、问题分析
（一）问题的类型
贪心算法AND动态规划
贪心算法：把一个大问题分解成一个个子问题，希望通过局部最优解来获得全局最优解，但是不能保证给出全局最优解，而且有时候即使问题有解贪心算法给出的仍然是无解；
动态规划和贪心的区别之一在于：只要问题有解，动态规划就能够给出最优解
For instance:
1.Given:Coins={1,8,13},16cents=?
Greedy solution:4 coins:13+1+1+1
Optimal solution:2 coins:8+8
2.Given:Coins={2,8,15},24cents=?
Greedy solution:no solution:coins:15+8+?
Optimal solution:3 coins:8+8+8
所以硬币问题需要采用动态规划来解决（当然你也可以采用递归来求解，但相比之下递归求解时，重叠子问题很多，所以导致整个算法时间复杂度不太理想）
（二）动态规划求解过程
1、确定状态
（1）最后一步
虽然我们不知道最优解是什么，但是最优策略肯定是k枚硬币COIN1,COIN2,COIN3…COINk,这些硬币的面值加起来刚好等于我们需要的总金额M，所以一定有最后一枚硬币COINk，去掉这枚硬币，前面的硬币面值加起来是M-COINk
（2）子问题
我们不关心前面的k-1枚硬币是如何凑成M-COINk的，现在也不知道COINk和k具体是什么，但是k-1枚硬币凑出了M-COINk是可以确定的，因为要求最优解，所以凑成M-COINk的硬币数量也一定是最少的（不理解的可以用反证法证一下）；
所以我们接下来求：用最少的硬币凑成M-COINk,原问题是最少硬币凑成M，这样一来我们就把原问题化成了一个子问题，问题的规模就缩小了，我们假设状态
f(X)=最少用多少枚硬币拼出X
接下来看那最后一枚硬币是多少？问题开始前我已经把问题具体化了（M=11，硬币面值有{1，3，5}）所以这里的最后一枚硬币COINk只能是1，3，或者5；
如果COINk=1, f(11)=f(11-1)+1(加上最后一枚硬币1)；
如果COINk=3, f(11)=f(11-3)+1(加上最后一枚硬币3)；
如果COINk=5, f(11)=f(11-5)+1(加上最后一枚硬币5)；
除此之外没有其他可能性了
需要求最少的硬币数，所以：
f(11)=min{f(11-1)+1,f(11-3)+1,f(11-5)+1}
2、转移方程
动态规划我们一般要用到数组来写状态转移方程
设状态f[X]=最少用多少枚硬币拼出X
对于任意的X，都有
f[x]=min{f[X-1]+1,f[X-3]+1,f[X-5]+1}
3、初始状态和边界条件
f[x]=min{f[X-1]+1,f[X-3]+1,f[X-5]+1}
先思考两个问题
问题1：X-1,X-3,X-5小于0的情况应该怎么办？
问题2：什么时候停下来？
解决问题：
如果拼不出来values,就定义f[values]=正无穷，如：f[-1]=f[-2]=正无穷
初始条件：f[0]=0;
计算后面的值，我们需要用到f[0],但是如果用转移方程来计算我们会得到正无穷，可是实际上f[0]=0;边界情况其实就是不要数组越界。
4.计算顺序
拼出X所需的最少硬币数：
f[x]=min{f[X-1]+1,f[X-3]+1,f[X-5]+1}
初始条件：f[0]=0;
然后计算f[1],f[2]…f[11]
当我们计算f[X]时，f[X-1],f[X-3],f[X-5]都已经得到结果了
计算顺序的确定原则：当我们用计算等式左边时，右边用到的状态都已经算过了
三、代码实现
1.Java代码（附运行结果）
public class coinChange {
//{1,3,5} //M=11
public static int coin(int[] a,int M){
int [] f=new int[M+1];
int n=a.length;//number of kinds of coins
//initialization
f[0]=0;
int i,j;
//f[1],f[2]...f[11]
for(i=1;i<=M;i++)
{
f[i]=Integer.MAX_VALUE;
//last coin a[j]
//f[i]=min{f[i-a[0]]+1...f[i-a[n-1]]+1}
for(j=0;j<n;++j)
{
if(i>=a[j] && f[i-a[j]]!=Integer.MAX_VALUE){
f[i]=Math.min(f[i-a[j]]+1,f[i]);
}
}
}
if(f[M]==Integer.MAX_VALUE){
f[M]=-1;
}
return f[M];
}
public static void main(String[] args)
{
int []a={1,3,5};
int M=11;
int coins_number=coin(a,M);
System.out.println(coins_number);
}
}
运行结果
2.C语言代码（附运行结果）
#include<stdio.h>
int coinChange(int* coins, int coinsSize, int values) {
int* dp = (int*)calloc(values + 1, sizeof(int));
int i, j;
for (i = 0; i <= values; i++)
{
dp[i] = values + 1;//初始化
}
dp[0] = 0;
for (i = 0; i <= values; i++) {
for (j = 0; j < coinsSize; j++)
{
if (i < coins[j])
continue;
dp[i] = dp[i] < dp[i - coins[j]] + 1 ? dp[i] : dp[i - coins[j]] + 1;
}
}
return (dp[values] != values + 1) ? dp[values] : -1;
}
int main(void)
{
int coins[] = { 1,3,5 };
int coinsSize = 3;
int values = 11;
int num = coinChange(coins, coinsSize, values);
printf("最少需要%d枚硬币\n", num);
return 0;
}
运行结果