【LeetCode 热题 100】322. 零钱兑换——（解法二）自底向上

Problem: 322. 零钱兑换

整体思路

这段代码同样旨在解决 “零钱兑换” 问题，但它采用的是一种 自底向上（Bottom-Up）的动态规划 方法，也称为 迭代法 或 制表法 (Tabulation)。这种方法通过构建一个DP表，从最小的子问题开始，逐步计算出最终的解，避免了递归的开销。

该实现方式是解决完全背包问题的标准二维DP模型。

1. 问题模型：完全背包

   • 底层模型依然是 完全背包问题。

2. 状态定义与索引映射

   • 算法定义了一个二维DP数组 dp。
   • dp[i][j] 的含义是：只使用前 i 种硬币（从 coins[0] 到 coins[i-1]）来凑成金额 j 时，所需的最少硬币数量。
   • 这是一个常见的索引偏移技巧，dp 的第一维 i+1 对应 coins 的索引 i。

3. DP表的计算

   • 基础情况 (Base Case)：
     • dp[0][j]：表示用0种硬币来凑金额 j。
     • Arrays.fill(dp[0], Integer.MAX_VALUE / 2)：将第0行（除了dp[0][0]）填充为极大值，表示用0种硬币无法凑成任何非0的金额。
     • dp[0][0] = 0：用0种硬币凑成金额0，需要0个硬币。这是整个DP计算的起点。
   • 状态转移 (State Transition)：
     • 算法使用两层嵌套循环来填充DP表。
     • 外层循环 for (int i = 0; i < n; i++) 遍历“物品”，即每一种硬币 coins[i]。
     • 内层循环 for (int j = 0; j <= amount; j++) 遍历“背包容量”，即目标金额 j。
     • 对于每个状态 dp[i+1][j]，它根据是否选择硬币 coins[i] 来更新：
       • if (j < coins[i]): 如果当前目标金额 j 小于硬币 coins[i] 的面额，那么 coins[i] 肯定不能用。此时，dp[i+1][j] 的值只能等于不考虑 coins[i] 的情况，即 dp[i][j]。
       • else: 如果 j >= coins[i]，我们有两个选择：
         1. 不选 coins[i]：最少数量为 dp[i][j]。
         2. 选 coins[i]：最少数量为 dp[i+1][j - coins[i]] + 1。注意这里是 dp[i+1] 而不是 dp[i]，因为这是完全背包，coins[i] 可以重复选。
            dp[i+1][j] 就取这两者的最小值。

4. 返回结果

   • 当所有循环结束后，dp[n][amount] 中就存储了用所有 n 种硬币凑成 amount 所需的最少数量。
   • 最后，检查这个值是否是极大值，如果是，则表示无法凑成，返回-1；否则返回该值。

完整代码

import java.util.Arrays;class Solution {/*** 计算凑成总金额所需的最少的硬币个数。* @param coins 硬币面额数组* @param amount 总金额* @return 最少硬币数，如果无法凑成则返回 -1*/public int coinChange(int[] coins, int amount) {int n = coins.length;// dp: 二维DP表。dp[i][j] 表示用前 i 种硬币凑成金额 j 的最少数量。int[][] dp = new int[n + 1][amount + 1];// 基础情况：用0种硬币凑成非0金额是不可能的，设为极大值。Arrays.fill(dp[0], Integer.MAX_VALUE / 2);// 基础情况：用0种硬币凑成金额0，需要0个。dp[0][0] = 0;// i 对应 coins 数组的索引，代表“物品”。for (int i = 0; i < n; i++) {// j 代表“背包容量”，即目标金额。for (int j = 0; j <= amount; j++) {// 如果目标金额 j 小于当前硬币 coins[i] 的面额，则无法使用该硬币。// 此时 dp[i+1][j] 的值等于不考虑 coins[i] 的情况，即 dp[i][j]。if (j < coins[i]) {dp[i + 1][j] = dp[i][j];} else {// 如果可以使用，则在“不使用”和“使用”之间做选择：// dp[i][j]: 不使用 coins[i] 的最少数量。// dp[i+1][j - coins[i]] + 1: 使用至少一个 coins[i] 的最少数量。dp[i + 1][j] = Math.min(dp[i][j], dp[i + 1][j - coins[i]] + 1);}}}// 最终答案存储在 dp[n][amount] 中。int ans = dp[n][amount];// 如果 ans 仍是极大值，说明无法凑成，返回 -1。return ans < Integer.MAX_VALUE / 2 ? ans : -1;}
}

时空复杂度

时间复杂度：O(N * Amount)

1. 循环结构：算法使用了两层嵌套循环。
   • 外层 for 循环遍历 coins 数组，执行 N 次。
   • 内层 for 循环从 0 遍历到 amount，执行 amount + 1 次。
2. 计算依据：
   • 总的操作次数是内外层循环次数的乘积，即 N * (amount + 1)。

综合分析：
算法的时间复杂度为 O(N * Amount)。

空间复杂度：O(N * Amount)

1. 主要存储开销：算法创建了一个二维 dp 数组来存储所有子问题的解。
2. 空间大小：该数组的大小是 (N + 1) * (amount + 1)。

综合分析：
算法所需的额外空间主要由 dp 数组决定，其空间复杂度为 O(N * Amount)。

空间优化提示：
观察状态转移 dp[i+1][j] = min(dp[i][j], dp[i+1][j - coins[i]] + 1)，可以发现 dp[i+1] 这一行的计算只依赖于 dp[i]（上一行）和 dp[i+1]（本行已计算的部分）。这符合滚动数组的优化条件。我们可以将二维 dp 数组压缩为一维，将空间复杂度从 O(N * Amount) 优化到 O(Amount)。