# 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 鼓励我一下：
觉得还不错的话，给我的项目点个star吧