322. 零钱兑换

[此处请插入：动态规划（DP）状态转移过程示意图]

✨核心逻辑

本题采用 动态规划（完全背包问题） 的策略：

状态定义：定义一维数组 dp，其中 dp[i] 表示凑齐总金额为 i 所需的最少硬币数量。
初始化：因为硬币面额最小为 1，凑齐任意金额最多只需要 amount 枚硬币。所以我们可以将 dp 数组的初始值全部设为 amount + 1（一个不可能达到的“无穷大”值）。数组默认值 dp[0] = 0，表示凑齐 0 元需要 0 枚硬币，这是状态转移的起始点。
状态转移方程：外层循环从 1 遍历到 amount，内层循环遍历每种面额的硬币 coin。如果当前硬币面额小于等于目标金额 i，则可以将当前硬币加入到凑齐 i - coin 的方案中，比较并更新 dp[i]： dp[i] = Math.min(dp[i], dp[i - coin] + 1)
最终判断：如果遍历结束后，dp[amount] 的值仍然是初始化的 amount + 1，说明没有任何一种硬币组合能组成总金额，返回 -1；否则返回 dp[amount]。

🔥代码实现（含详细变量注释）

public static int coinChange(int[] coins, int amount) {
    // dp ： 状态的存储，以及后续的答案建立在原有的状态之上
    // 第一步：定义 dp
    // dp[i]表示凑齐第 i 元的最少硬币数量
    // dp[amount] 即为 amount 面额的答案
    int[] dp = new int[amount + 1];
    
    // 第二步: 状态如何转移呢？
    // 根据面额，找当前答案的上一步
    // 1. 初始化元素为 amount + 1，答案最大的值为 amount（全用1元），不可能为 amount + 1，充当“无穷大”的作用
    for (int i = 1; i < dp.length; i++) {
        dp[i] = amount + 1;
    }

    // 遍历每一个金额
    for (int i = 1; i < dp.length; i++) {
        // 遍历每一种可用的硬币面额
        for (int coin : coins) {
            // 如果当前硬币面额小于等于当前需要凑齐的金额 i，说明可以用这枚硬币
            if (coin <= i) {
                // 状态转移：尝试用当前的硬币去凑齐金额 i，
                // 比较原来的方案和用当前硬币的方案（凑齐 i - coin 的硬币数 + 1），取较小值
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    // 如果 dp[amount] 仍然是初始化的 amount + 1，说明无法凑齐，返回 -1；否则返回最少硬币数
    return dp[amount] == amount + 1 ? -1 : dp[amount];
}

⏱️复杂度分析
- 时间复杂度：O(S * N)，其中 S 是金额总数 amount，N 是硬币的种类数 coins.length。我们需要遍历 S 个状态，并在每个状态中尝试 N 种硬币。
- 空间复杂度：：O(S)。我们需要一个长度为 amount + 1 的数组 dp 来存储不同金额的最少硬币数。

总题思路汇总：

1.定义dp状态，dp[i] 代表的是什么含义呢？？