LeetCode-322. 零钱兑换 - sheep44044的小站

动态规划#

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

1
输入：coins = [1, 2, 5], amount = 11
2
输出：3
3
解释：11 = 5 + 5 + 1

示例 2：

1
输入：coins = [2], amount = 3
2
输出：-1

示例 3：

1
输入：coins = [1], amount = 0
2
输出：0

思路

相较于上题 279. 完全平方数 ，这题对物品的选取作了限制，以及可能无法返回-1的要求。

我们只需要最后dp[amount] == math.MaxInt32进行校验即可，因为dp[i]如果没有正常值，会因为math.MaxInt32 < math.MaxInt32+1保持这个值。

其他逻辑一样

1
func coinChange(coins []int, amount int) int {
2
    dp := make([]int, amount+1)
3

4
    dp[0] = 0
5
    for i := 1; i <= amount; i++ {
6
        dp[i] = math.MaxInt32
7
    }
8

9
    for i := 0; i <= amount; i++ {
10
        for j := 0; j < len(coins); j++ {
11
            if coins[j] <= i {
12
                dp[i] = min(dp[i], dp[i-coins[j]]+1)
13
            }
14
        }
15
    }
16

17
    if dp[amount] == math.MaxInt32 {
18
        return -1
19
    }
20
    return dp[amount]
21
}

思路

令一种写法先物品，后容量

1
func coinChange(coins []int, amount int) int {
2
    // 1. 定义并初始化 dp 数组
3
    dp := make([]int, amount+1)
4
    dp[0] = 0
5
    for i := 1; i <= amount; i++ {
6
        dp[i] = math.MaxInt32
7
    }
8

9
    // 2. 完全背包标准遍历：外层遍历物品(硬币)，内层正序遍历背包(金额)
10
    for i := 0; i < len(coins); i++ {
11
        for j := coins[i]; j <= amount; j++ {
12
            // 3. 拦截溢出：只有当去掉了当前硬币的剩余金额是“可达的”，才进行计算
13
            if dp[j-coins[i]] != math.MaxInt32 {
14
                // 4. 状态转移
15
                dp[j] = min(dp[j], dp[j-coins[i]]+1)
16
            }
17
        }
18
    }
19

20
    // 5. 循环结束后，统一结算：如果最终目标金额还是极大值，说明彻底凑不出，返回 -1
21
    if dp[amount] == math.MaxInt32 {
22
        return -1
23
    }
24

25
    return dp[amount]
26
}