猿辅导面试题 Leetcode 322. 零钱兑换I & II

Leetcode 322. 零钱兑换 I

本题要求计算凑成给定总金额所需的最少硬币个数，属于典型的动态规划问题。

初始化：创建一个动态规划数组 dp，其中 dp[i] 表示凑成金额 i 所需的最少硬币数。初始时，dp 数组的所有元素设为 amount + 1（表示不可达），仅 dp[0] 设为 0（表示金额 0 无需硬币）。
动态规划填充：对于每个金额 i（从 1 到 amount），遍历所有硬币面额。若当前金额 i 减去硬币面额 coins[j] 非负，则更新 dp[i] 为 dp[i - coins[j]] + 1 和当前 dp[i] 中的较小值。
结果返回：最后检查 dp[amount] 是否仍为初始值 amount + 1，若是则返回 -1（表示无法凑成），否则返回 dp[amount]。

Leetcode 518. 零钱兑换 II

本题要求计算凑成给定总金额的硬币组合数，属于完全背包问题的变体。

初始化：创建一个二维动态规划数组 dp，其中 dp[i][j] 表示使用前 i 种硬币凑成金额 j 的组合数。初始化时，dp[0][0] 设为 1（表示金额 0 有一种组合方式），其余 dp[i][0] 也设为 1（因为金额 0 无需任何硬币即可凑成）。
动态规划填充：对于每种硬币（从 1 到 n），遍历所有金额（从 1 到 amount）。若当前金额 j 减去硬币面额 coins[i-1] 非负，则 dp[i][j] 更新为 dp[i-1][j] + dp[i][j-coins[i-1]]（即不使用当前硬币的组合数加上使用当前硬币的组合数）；否则，dp[i][j] 等于 dp[i-1][j]（即不使用当前硬币的组合数）。
状态压缩：为优化空间，可将二维数组压缩为一维数组 dp，其中 dp[j] 表示凑成金额 j 的组合数。初始化时，仅 dp[0] 设为 1。在遍历硬币和金额时，更新 dp[j] 为 dp[j] + dp[j-coins[i-1]]。
结果返回：最后返回 dp[amount]，即凑成目标金额的组合数。

时间复杂度：对于零钱兑换 II 问题，时间复杂度为 O(nm)，其中 n 是硬币种类数，m 是目标金额。

热门标签