322 零钱兑换 | 前端进阶积累

# 322 零钱兑换

# 题目链接

# 难度：中等

# 思路分析：

动态规划

# 想

# 一

# 想

# 再

# 看

# 答

# 案

# 想

# 一

# 想

# 再

# 看

# 答

# 案

# 代码：

自底而上动态规划从头开始找最优解

var coinChange = function(coins, amount) {
  let dp = new Array(amount + 1).fill(Infinity); // 初始无限大 再比较的时候 会使用零钱次数
  dp[0] = 0;
  // 所有零钱种类
  for (let coin of coins) {
    // 总金额
    for (let i = 1; i <= amount; i++) {
      if (i - coin >= 0) {
        // 总金额大于零钱
        // dp[i - coin] + 1 当前零钱需要的次数
        // dp[i] 其他零钱种类的最少次数
        // 如果前面的找不到最优解 会变为Infinity
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  console.log("res", dp);
  // 如果没找到 返回-1
  return dp[amount] === Infinity ? -1 : dp[amount];
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 鼓励我一下：

觉得还不错的话，给我的项目点个star吧

# 点个Star支持我一下~