题目

题目

思路

回溯 - 自上而下

第一眼想的是贪心，但需要准确凑出amount，所以贪心不可能
或许也是可能的？类似于排列组合的回溯，每次选择可以选择的集合中的最大的，不行就回溯，但由于需要准确的，所以也不用选择最大的，需要全部遍历一遍。
转换成递归，即solution(n) = 1 + solution(n - coin[i]), 其中取使结果最小的i
数据结构：需要一个int[amount]在递归间记录和传递solution(n - coin[i])，避免重复计算。

public class Solution {
  public int coinChange(int[] coins, int amount) {
    if(amount < 1) {
      return 0;
    }
    return coinChange(coins, amount, new int[amount]);
  }
  private int coinChange(int[] coins, int rem, int[] count) {
    if (rem < 0) {
      return -1;
    }
    if (rem == 0) {
      return 0;
    }
    if (count[rem - 1] != 0) {
      return count[rem - 1];
    }
    int min = Integer.MAX_VALUE;
    for (int coin : coins) {
      int res = coinChange(coins, rem - coin, count);
      if (res >= 0 && res < min) {
        min = res;
      }
    }
    count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min + 1;
    return count[rem - 1];
  }
}

动态规划 - 自下而上

状态转移方程

public class Solution {
  public int coinChange(int[] coins, int amount) {
    // 代表凑不出的情况，因为可能的最大数量amount个面值为1的coins，妙啊， 同时和dp[0]=0区分来实现精准凑数的目的，太妙了
    int max = amount + 1;
    // 可以只用amount大小，但是为了下标方便，同时将amount==0的情况包括进去
    int[] dp = new int[amount + 1];
    // 填充数组函数
    Arrays.fill(dp, max);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
      for (int j = 0; j < coins.length; j++) {
        if (coins[j] <= i) {
          // 需要多个coins凑的情况
          dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
        }
      }
    }
    return dp[amount] > amount ? -1 : dp[amount];
  }
}