LeetCode (2) 凑零钱

请注意，本文编写于 1057 天前，最后修改于 1057 天前，其中某些信息可能已经过时。

题目

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

你可以认为每种硬币的数量是无限的。

示例 1：

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

https://leetcode-cn.com/problems/coin-change/

方法

递归
动态规划

解题思路

递归

递归结束条件

如果你学习过递归，那么首先每次使用递归都需要知道它的结束条件，这里的结束条件是

if (amount == 0) {
     return 0;
   }

余额为0 结束递归。

约束条件

剩下的钱无法被某些大额硬币凑整，即amount - coin < 0的场景
凑不整的场景需要返回-1
需要比较每一种硬币凑出来的数量的最小值，即 min{f(x-1),f(x-2),f(x-5)}

动态规划

可以参见知乎的介绍：

https://www.zhihu.com/question/23995189

https://www.zhihu.com/question/323076638

动态规划本质是状态的转移与优化，每一个动态规划问题中我们都需要寻找到他的转移方程。

解题步骤

递归

见解题思路

剪枝递归

我们使用了递归成功解决了问题，但是原始的递归会出现执行超时，因为会出现重复计算，所以需要一个字典来帮助我们记录计算过的数据，所以我们需要引入一个一维数组来记录这些数据，当一维数组有对应的解就直接返回不再做递归计算！相当于给递归做了剪枝处理。

动态规划

最小问题：当金额为0时需要的硬币为0。继而递推当金额为1时，需要最少硬币为f(0)+1，当金额为2时，需要硬币为min{f(0)+1,f(1)+1}，以此类推...
找到转移方程min{f(x-1),f(x-2),f(x-5)}->min{f(x-coin)},coin∈{1,2,5}

完整代码

递归

package org.chenly.study;

/**
 * 凑零钱问题
 *
 * @author chenly
 * @create 2020-10-28 23:26
 */
public class CoinQuestion {

   public static void main(String[] args) {
      int[] coins = new int[] { 1, 2, 5 };
      System.out.println(coinChange(coins, 11));

   }

   public static int coinChange(int[] coins, int amount) {
      if (amount == 0) {
         return 0;
      }
      int min = Integer.MAX_VALUE;
      for (int coin : coins) {
         //如果存在余额不足以用零钱凑，否决该方案
         if (amount - coin < 0) {
            continue;
         }
         //计算剩下的零钱每一种硬币凑出来的次数
         int tmp = coinChange(coins, amount - coin);
         //排除掉凑不出来的场景
         if (tmp == -1) {
            continue;
         }
         //比较每一个硬币的可凑出来的最少次数
         min = Math.min(tmp + 1, min);
      }
      //如果是初始值那么一定是凑不出来，返回-1
      return min == Integer.MAX_VALUE ? -1 : min;
   }

}

剪枝递归

package org.chenly.study;

/**
 * 凑零钱问题
 *
 * @author chenly
 * @create 2020-10-28 23:26
 */
public class CoinQuestion {

   public static void main(String[] args) {
      int[] coins = new int[] { 186, 419, 83, 408 };
      System.out.println(coinChange(coins, 6249));

   }

   public static int[] table = null;

   public static int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        if (table == null) {
            table = new int[amount + 1];
            for (int i = 0; i < amount + 1; i++) {
                table[i] = Integer.MAX_VALUE;
            }
        }
        if (table[amount] != Integer.MAX_VALUE) {
            return table[amount];
        }
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            //如果存在余额不足以用零钱凑，否决该方案
            if (amount - coin < 0) {
                continue;
            }
            //计算剩下的零钱每一种硬币凑出来的次数
            int tmp = coinChange(coins, amount - coin);
            //排除掉凑不出来的场景
            if (tmp == -1) {
                continue;
            }
            //取得凑出来的最少次数
            min = Math.min(tmp + 1, min);
        }
        //如果是初始值那么一定是凑不出来，返回-1
        int minLoop = min == Integer.MAX_VALUE ? -1 : min;
        table[amount] = minLoop;
        return minLoop;
   }

}

动态规划

给出两种解法，原理是一样的，只是一个自上而下的扣除法一个是累加法。

参考：https://leetcode-cn.com/problems/coin-change/solution/java-dp-solution-onm-by-i-superman/

package org.chenly.study;

/**
 * @author chenly
 * @create 2020-10-31 10:25
 */
public class Ques {
   public static void main(String[] args) {

      int[] coins = new int[] { 1, 2147483647 };
      System.out.println(coinChange(coins, 2));
   }

   /**
    * 动态规划
    * 这里的解法是采用扣除法，当然你也可以采用累加法
    */
   /*private static int coinChange(int[] coins, int amount) {
      //定义存储在不同金额时候的最小凑整次数
      int[] table = new int[amount + 1];
      //记住，table[amount] 不要赋值，
      //最小问题，表示在不做硬币扣除，需要的硬币个数为0
      for (int i = 0; i < amount; i++) {
         table[i] = Integer.MAX_VALUE;
      }
      for (int i = amount; i > 0; i--) {
         for (int coin : coins) {
            //当该值还没被求出时，跳过
            if (table[i] == Integer.MAX_VALUE) {
               continue;
            }
            //不能被凑整的场景也需要跳过
            if (i - coin < 0) {
               continue;
            }
            //比较出是否还有没有比当前存储在数组中的值还要小的计算次数
            table[i - coin] = Math.min(table[i] + 1, table[i - coin]);
         }
      }
      //table[0]没有被赋值说明这个金额无法被凑整
      return table[0] == Integer.MAX_VALUE ? -1 : table[0];
   }*/
   
   private static int coinChange(int[] coins, int amount) {
      //定义存储在不同金额时候的最小凑整次数
      int[] table = new int[amount + 1];
      //记住，table[0] 不要赋值，
      //表示金额为0 时需要的硬币为0个
      for (int i = 1; i <= amount; i++) {
         table[i] = Integer.MAX_VALUE;
      }

      for (int i = 0; i < amount; i++) {
         for (int coin : coins) {
            //当该值还没被求出时，跳过
            if (table[i] == Integer.MAX_VALUE) {
               continue;
            }
            //不能被凑整的场景也需要跳过
            //不能使用i+coin>amount,在测试用例中有存在coin值为int最大值的场景，为了不溢出，用减法
            if (i > amount - coin) {
               continue;
            }
            //比较出是否还有没有比当前存储在数组中的值还要小的计算次数
            table[i + coin] = Math.min(table[i] + 1, table[i + coin]);
         }
      }

      //table[amount]没有被赋值说明这个金额无法被凑整
      return table[amount] == Integer.MAX_VALUE ? -1 : table[amount];
   }
}

算法学习项目

https://github.com/fzustone/studyAlg

LeetCode

已有 2 条评论

阿菜菜

2020-12-02 17:22

0 0

有一个以为，说当 amount=1 的时候，需要1枚硬币，这个1枚硬币是在题目给定了 coins 里面选的，那才是1枚。为什么可以推算出 f(2) = f(1) + 1 ?

chenly 回复 @阿菜菜

2020-12-02 22:06

这其实是一个递归思想，假设存在一个函数f(x)可以得到剩下的最小凑整硬币，amount=0,硬币数量是0,那么amount=1，其实可以写成f(0)+1，需要一枚硬币，amount=2，那么你凑出来的方式可以是f(1)+1【先用一枚1元的硬币，再用一个一元硬币】，你也可以直接f(0)+1,也就是用一枚2元的硬币直接达成目的，从上到下递归下去，不用关心剩余的钱是怎么凑的，剔除无法凑整的，得到可以凑出来的方案中选出最小的方案

题目

方法

解题思路

递归

递归结束条件

约束条件

动态规划

解题步骤

递归

剪枝递归

动态规划

完整代码

递归

剪枝递归

动态规划

算法学习项目

设计模式(5)-代理模式（Proxy Pattern）

JDK动态代理

添加新评论

已有 2 条评论