动态规划之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;
}

运行结果

结束：最近刚学的动态规划，记录一下，有不足的还请指出，大家共同进步！