【动态规划】Leetcode 279. 完全平方数【中等】

完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

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

解题思路

• 1、使用动态规划求解，定义一个一维数组dp，其中dp[i]表示和为i的完全平方数的最少数量。
• 2、初始化数组dp，长度为n + 1，全部初始化为最大值，dp[0]为0。
• 3、对于每个数字i，遍历从1到sqrt(i)的完全平方数j*j，更新dp[i]为dp[i - j * j] + 1和dp[i]中的较小值。
  动态规划的状态转移方程为：

•   dp[i] = min(dp[i], dp[i - j * j] + 1)，其中 1 <= j * j <= i
  1

  这个方程的意思是，如果当前的数 i 可以由 j * j 和 i - j * j 组成，那么 dp[i] 就可以通过 dp[i - j * j] + 1 来更新，即将 j * j 加入到和为 i 的完全平方数的组合中。
• 4、最终返回dp[n]即可。

Java实现

public class PerfectSquares {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        /**
         * 首先，定义一个数组 dp[]，其中 dp[i] 表示组成数值 i 的最小平方数数量。
         *
         * 然后，通过两层循环遍历所有可能的数值 i，从 1 到 n。
         *
         * 内层循环中，对于当前数值 i，我们尝试找到组成它的最小平方数数量。
         * 我们遍历所有小于等于 i 的平方数，记为 j * j，并更新 dp[i] 的值为
         * dp[i - j * j] + 1 的最小值。也就是说，我们找到了一个平方数 j * j，
         * 并尝试用它去更新 i 的最小平方数数量，看是否可以得到更优的解。
         *
         * 最终，当外层循环结束时，dp[n] 中存储的就是组成数值 n 的最小平方数数量。
         * 这种解法的核心思想是利用动态规划的思想，
         * 通过计算子问题的最优解来构建更大规模问题的最优解。
         * 通过从小到大的顺序计算所有可能的数值 i，我们可以确保在计算 dp[i] 时，
         * dp[i - j * j] 已经计算过了，并且存储了正确的结果，
         * 从而确保每个状态的最优解被正确计算出来。
         */
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        
        return dp[n];
    }

    public static void main(String[] args) {
        PerfectSquares ps = new PerfectSquares();
        int n = 12;
        System.out.println("Minimum number of perfect squares: " +
                ps.numSquares(n)); // Output: 3 (12 = 4 + 4 + 4)
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

时间空间复杂度

• 时间复杂度：外层循环遍历了n次，内层循环遍历了sqrt(n)次，时间复杂度为O(n * sqrt(n))。

• 空间复杂度：使用了长度为n + 1的数组dp，空间复杂度为O(n)。