Leetcode 279.完全平方数

题目要求

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

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

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

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

动态规划

动规五部曲
跟上一道题《零钱兑换》基本一致，只不过零钱的价值是完全平方数。

  1. 确定dp数组（dp table）以及下标的含义
    dp[j]表示和为j的完全平方数的最少数量

  2. 确定递推公式
    dp[j] = Math.min(dp[j], dp[j - i*i] + 1)

  3. dp数组如何初始化
    dp[0] = 0
    因为后续要比较取最小值，所以其他值初始化为一个较大的数——Integer.MAX_VALUE

  4. 确定遍历顺序
    正着遍历，完全平方数可以重复使用

  5. 举例推导dp数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];

        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = i*i; j <= n; j++) {
                // if判断可以省略，因为在完全平方数这一题不会有"凑不成"的状况发生（ 一定可以用"1"来组成任何一个n）
                // 故可以省略掉这个if判断
                //if (dp[j - i*i] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[j - i*i] + 1);
                //}
            }
        }
        return dp[n];
    }
}