image.png

题解

1.动态规划-自上而下

优化版 已经求解过的缓存起来

  1. function coinChange(coins: number[], amount: number): number {
  2.     let cache = {};
  3.     const dp = (n) => {
  4.         if (cache[n]) return cache[n];
  5.         if (n == 0) return 0;
  6.         if (n < 0) return -1;
  7.         let res = Number.MAX_SAFE_INTEGER;
  8.         for (let i = 0; i < coins.length; i++) {
  9.             let sub = dp(n - coins[i]);
  10.             if(sub === -1) continue;
  11.             res = Math.min(res, sub + 1);
  12.         }
  13.         if (res === Number.MAX_SAFE_INTEGER) {
  14.             cache[n] = -1;
  15.         } else {
  16.             cache[n] = res;
  17.         }
  18.         console.log(cache);
  19.         return cache[n];
  20.     }
  21.     return dp(amount);
  22. }

1.动态规划-自下而上

function coinChange(coins: number[], amount: number): number {
    let dp = new Array(amount + 1).fill(amount + 1);
    dp[0] = 0;
    for (let i = 1; i <= amount; i++) {
        for (let j = 0; j < coins.length; j++) {
            if (coins[j] <= i) {
                dp[i] = Math.min(dp[i], dp[i - coins[j]]+1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
};