前言

Github:https://github.com/HealerJean

博客:http://blog.healerjean.com

1、零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。

示例 1:


输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1

示例 2:

输入: coins = [2], amount = 3
输出: -1

1.1、解题思路

假设你是个土豪,你有1,5,10,20,50,100的钞票,你要凑出666买瓶水喝,依据生活经验,我们一般采取这样的策略:能用100就用100的,否则就用50的,依此类推,在这种策略下,666=100*6 + 50 1 + 10 1 + 51 + 11, 一共用了10张钞票。

这种策略就称为 贪心策略 :贪心策略是在当前情况下做出最好的选择。

根据需要凑出的金额来进行贪心,但是,如果我们换一组钞票面值,比如 1, 5, 11,我们要凑出15的时候, 贪心策略就会出错:

15 = 11 * 1 + 1 * 4 (贪心策略)

15 = 5 * 3(正确策略)

贪心策略哪里出错了? 鼠目寸光

重新分析刚刚的例子。

w=15时,

如果取11,接下来就面对w=4的情况;

如果取5,则接下来面对w=10的情况。

我们发现这些问题都有相同的形式:“给定w,凑出w所用的最少钞票是多少张?” 接下来,我们用f(n)来表示“凑出n所需的最少钞票数量”。  

那么,如果我们取11, 利用11来凑出15,付出的代价等于f(4)加上自己这一张钞票。现在我们暂时不管f(4)怎么求出来。依次类推,

 

那么,现在w=15的时候,我们该取那种钞票呢?当然是各种方案中,cost值最低的那一个

- 取11: cost=  f(4)  + 1     = 4 + 1 = 5 
- 取5:  cost = f(10) + 1     = 2 + 1 = 3
- 取1:  cost = f(14) + 1     = 4 + 1 = 5  

显而易见,cost值最低的是取5的方案。我们通过上面三个式子,做出了正确的决策!

这给了我们一个至关重要的启示—— 只与 相关;更确切地说: f(n) 只与 f(n-1),f(n-5),f(n-11) 相关;更确切地说:

f(n)=min{f(n-1),f(n-5),f(n-11)}+1:也就是说,最好从1开始将n求出来

1.2、算法

public int coinChange(int[] coins, int amount) {

    //凑出多少钱需要多少 ,为了好看 讲amout设置为数组的边界索引位
    int [] fox = new int[amount + 1];
    //从1块钱开始算,一直到凑出amount为止
    for(int i = 1; i <= amount; i++){
        int cost = Integer.MAX_VALUE;
        //遍历 现在的纸币
        for(int j = 0; j < coins.length; j++){
            //1、要凑的钱,必须大于等于目前的钱 才可能存在n
            // 2、如果 i > coins[j] 那么 fox[i - coins[j]] 可能不存在,所以也要加入判断
            if(i  >= coins[j]  && fox[i - coins[j]] != Integer.MAX_VALUE){
                cost = Math.min(cost, fox[i - coins[j]] + 1);
            }
        }
        //当上面不进入 if的时候,这里的fox[i] 可能为 Integer.MAX_VALUE
        fox[i] = cost;
    }
    return  fox[amount] == Integer.MAX_VALUE ? -1 : fox[amount];
}

1.3、测试

    @Test
    public void test(){
        int[] coins = {1,2,5};
        int amount = 11;
        System.out.println(coinChange(coins, amount));
    }

ContactAuthor