好的，我们来做一道经典的动态规划问题：LeetCode 第 322 题「零钱兑换」。

请注意，根据您提供的列表，第 322 题「零钱兑换」已经讲过了。为了避免重复，我将从列表中挑选一个尚未出现的经典题目。

我选择 LeetCode 第 279 题「完全平方数」。我们开始吧。

题目描述

LeetCode 279. 完全平方数

给定一个正整数 n，你的任务是找到最少的完全平方数（例如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要返回这个最少的数量。

如果 n 本身就是一个完全平方数，那么答案就是 1。

示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9

解题思路：循序渐进

这个问题可以用动态规划来解决。核心思想是：一个数 n 可以看作是由一个比它小的数 (n - k) 加上一个完全平方数 k 构成的。

步骤 1：定义状态

我们定义一个数组 dp，其中 dp[i] 表示和为 i 的完全平方数的最少数量。

我们的目标是计算 dp[n]。

步骤 2：确定初始状态

最简单的边界情况是 dp[0] = 0。因为和为 0 不需要任何平方数。

对于 i > 0，我们初始时可以假设一个最坏情况：即全部由 1（最小的完全平方数）构成，所以 dp[i] 的初始值可以设为 i（即 i 个 1 相加）。

步骤 3：状态转移方程

对于每一个 i（从 1 到 n），我们遍历所有可能的完全平方数 j * j，其中 j * j <= i。

对于每一个这样的平方数，我们考虑：如果我用掉一个 j * j，那么剩下的数值就是 i - j*j。那么，构成 i 的最少数量就是 1（代表这个 j*j）加上构成 i - j*j 的最少数量。

所以，状态转移方程是：
dp[i] = min(dp[i], dp[i - j*j] + 1)

步骤 4：计算顺序

我们从小到大计算 dp 数组，从 i = 1 一直计算到 i = n。这样可以确保在计算 dp[i] 时，dp[i - j*j] 已经被计算过了。

步骤 5：举例推导

我们以 n = 12 为例，手动推导一下 dp 数组。

1. dp[0] = 0
2. i = 1：
   • 可能的 j*j：1 (j=1)
   • dp[1] = min(dp[1], dp[1-1] + 1) = min(1, 0+1) = 1
3. i = 2：
   • 可能的 j*j：1
   • dp[2] = min(dp[2], dp[2-1] + 1) = min(2, 1+1) = 2 (即 1+1)
4. i = 3：
   • 可能的 j*j：1
   • dp[3] = min(dp[3], dp[3-1] + 1) = min(3, 2+1) = 3 (即 1+1+1)
5. i = 4：
   • 可能的 j*j：1, 4 (j=2)
   • 先考虑 1：dp[4] = min(4, dp[3] + 1) = min(4, 4) = 4
   • 再考虑 4：dp[4] = min(4, dp[0] + 1) = min(4, 1) = 1
   • 所以 dp[4] = 1
6. i = 5：
   • 可能的 j*j：1, 4
   • 考虑 1：dp[5] = min(5, dp[4] + 1) = min(5, 2) = 2
   • 考虑 4：dp[5] = min(2, dp[1] + 1) = min(2, 2) = 2
   • 所以 dp[5] = 2 (即 4+1)
7. ...（继续这个过程）
8. i = 12：
   • 可能的 j*j：1, 4, 9 (因为 16 > 12)
   • 考虑 1：dp[12] = min(12, dp[11] + 1)。假设我们已算出 dp[11] = 3 (9+1+1)，那么结果是 4。
   • 考虑 4：dp[12] = min(4, dp[8] + 1)。假设我们已算出 dp[8] = 2 (4+4)，那么结果是 3。
   • 考虑 9：dp[12] = min(3, dp[3] + 1) = min(3, 4) = 3。
   • 所以 dp[12] = 3 (即 4+4+4)，与示例一致。

步骤 6：算法实现（伪代码）

函数 numSquares(n):
    创建数组 dp，长度为 n+1，初始值 dp[0] = 0
    对于 i 从 1 到 n：
        dp[i] = i // 最坏情况，全部由1构成
        j = 1
        当 j*j <= i 时：
            dp[i] = min(dp[i], dp[i - j*j] + 1)
            j = j + 1
    返回 dp[n]

步骤 7：复杂度分析

• 时间复杂度：O(n * √n)。因为外层循环是 O(n)，内层循环的 j 最大到 √n。
• 空间复杂度：O(n)，用于存储 dp 数组。

总结

「完全平方数」问题是一个典型的动态规划应用。

1. 状态定义：dp[i] 表示和为 i 所需的最少完全平方数个数。
2. 基础情况：dp[0] = 0。
3. 状态转移：对于每个数 i，尝试所有小于等于 i 的完全平方数 s = j*j，则 dp[i] 可以是 1 + dp[i - s] 中的最小值。
4. 计算顺序：自底向上，从小数算到大数。

这种方法可以确保我们高效且正确地找到最优解。