322. 零钱兑换

动态规划

  1.     public int coinChange(int[] coins, int amount) {
  2.         // 自底向上的动态规划
  3.         if(coins.length == 0){
  4.             return -1;
  5.         }
  7.         // memo[n]的值： 表示的凑成总金额为n所需的最少的硬币个数
  8.         int[] memo = new int[amount+1];
  9.         // 给memo赋初值，最多的硬币数就是全部使用面值1的硬币进行换
  10.         // amount + 1 是不可能达到的换取数量，于是使用其进行填充
  11.         Arrays.fill(memo,amount+1);
  12.         memo[0] = 0;
  13.         for(int i = 1; i <= amount;i++){
  14.             for(int j = 0;j < coins.length;j++){
  15.                 if(i - coins[j] >= 0){
  16.                     // memo[i]有两种实现的方式，
  17.                     // 一种是包含当前的coins[i],那么剩余钱就是 i-coins[i],这种操作要兑换的硬币数是 memo[i-coins[j]] + 1
  18.                     // 另一种就是不包含，要兑换的硬币数是memo[i]
  19.                     memo[i] = Math.min(memo[i],memo[i-coins[j]] + 1);
  20.                 }
  21.             }
  22.         }
  24.         return memo[amount] == (amount+1) ? -1 : memo[amount];
  25.     }
  27. //作者：sugar666
  28. //链接：https://leetcode-cn.com/problems/coin-change/solution/javadi-gui-ji-yi-hua-sou-suo-dong-tai-gui-hua-by-s/

记忆法

  1.     int[] memo;
  2.     public int coinChange(int[] coins, int amount) {
  3.         if(coins.length == 0){
  4.             return -1;
  5.         }
  6.         memo = new int[amount];
  8.         return findWay(coins,amount);
  9.     }
  10.     // memo[n] 表示钱币n可以被换取的最少的硬币数，不能换取就为-1
  11.     // findWay函数的目的是为了找到 amount数量的零钱可以兑换的最少硬币数量，返回其值int
  12.     public int findWay(int[] coins,int amount){
  13.         if(amount < 0){
  14.             return -1;
  15.         }
  16.         if(amount == 0){
  17.             return 0;
  18.         }
  19.         // 记忆化的处理，memo[n]用赋予了值，就不用继续下面的循环
  20.         // 直接的返回memo[n] 的最优值
  21.         if(memo[amount-1] != 0){
  22.             return memo[amount-1];
  23.         }
  24.         int min = Integer.MAX_VALUE;
  25.         for(int i = 0;i < coins.length;i++){
  26.             int res = findWay(coins,amount-coins[i]);
  27.             if(res >= 0 && res < min){
  28.                 min = res + 1; // 加1，是为了加上得到res结果的那个步骤中，兑换的一个硬币...
  29.             }
  30.         }
  31.         memo[amount-1] = (min == Integer.MAX_VALUE ? -1 : min);
  32.         return memo[amount-1];
  33.     }
  35. 作者：sugar666
  36. 链接：https://leetcode-cn.com/problems/coin-change/solution/javadi-gui-ji-yi-hua-sou-suo-dong-tai-gui-hua-by-s/

递归 超时

  1.     int res = Integer.MAX_VALUE;
  2.     public int coinChange(int[] coins, int amount) {
  3.         if(coins.length == 0){
  4.             return -1;
  5.         }
  7.         findWay(coins,amount,0);
  9.         // 如果没有任何一种硬币组合能组成总金额，返回 -1。
  10.         if(res == Integer.MAX_VALUE){
  11.             return -1;
  12.         }
  13.         return res;
  14.     }
  16.     public void findWay(int[] coins,int amount,int count){
  17.         if(amount < 0){
  18.             return;
  19.         }
  20.         if(amount == 0){
  21.             res = Math.min(res,count);
  22.         }
  24.         for(int i = 0;i < coins.length;i++){
  25.             findWay(coins,amount-coins[i],count+1);
  26.         }
  27.     }
  29. 作者：sugar666
  30. 链接：https://leetcode-cn.com/problems/coin-change/solution/javadi-gui-ji-yi-hua-sou-suo-dong-tai-gui-hua-by-s/