279. Perfect Squares

,

DFS

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) {
        Map<Integer, Integer> cache = new HashMap<>();
        return dfs(cache, n);
    }

    private int dfs(Map<Integer, Integer> cache, int n) {
        Integer count = cache.get(n);
        if (count != null) {
            return count;
        }

        count = n;
        for (int i = 1; i * i <= n; i++) {
            count = Math.min(count, 1 + dfs(cache, n - i * i));
        }

        cache.put(n, count);
        return count;
    }
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int numSquares(int n) {
        // 定义 dp[i] 为和为 i 的完全平方数的最小数量
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            dp[i] = i; // 最差情况下全部由 1 组成
            for (int j = 2; i - j * j >= 0; j++) { // 枚举所有可能的完全平方数
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 注意此处是加 1, 因为 j * j 为一个完全平方数
            }
        }

        return dp[n];
    }
}

References

279. Perfect Squares