LeetCode 279 - Perfect Squares

作者 QIFAN 日期 2017-01-02
LeetCode 279 - Perfect Squares

原题链接:279. Perfect Squares


题干

给定数字 n ,返回能组成 n 所需的最少平方数。

例子
输入:n = 13
返回:2
解释:13 = 4 + 9

输入:n = 12
返回:3
解释:12 = 4 + 4 + 4

思路

首先如果 n ≤ 0 ,返回 0 。

如果没有思路,可以先举例子来观察。

f(0) = 0
f(1) = 1(1)
f(2) = 2(1 + 1) = 1 + f(2 - 1)
f(3) = 3(1 + 1 + 1) = 1 + f(3 - 1)
f(4) = 1(4) = f(4) + f(0)
f(5) = 2(4 + 1) = 1 + min(f(5 - 1), f(5 - 4))
f(6) = 3(4 + 1 + 1) = 1 + min(f(6 - 1), f(6 - 4))
f(7) = 4(4 + 1 + 1 + 1) = 1 + min(f(7 - 1), f(7 - 4))
f(8) = 3(4 + 4) = 1 + min(f(8 - 1), f(8 - 4))
f(9) = 1(9) = 1 + min(f(9 - 1), f(9 - 4), f(9 - 9))

可以归纳出规律:f(n) = 1 + min(f(n - 1), f(n - 4), …, f(n - i i)), i i ≤ n

用文字解释就是:n 都可以用一个较小的数 m 加上一个平方数 kk 得到,kk 可以是从 1 到 n 的任一。因为要求最少,只需找出最小值。

base case:f(0) = 0, f(1) = 1
时间复杂度比 $O(n)$ 大一点吧。

代码:

public int numSquares(int n) {
int[] memo = new int[n + 1];
memo[0] = 0;
memo[1] = 1;
for (int i = 2; i <= n; i++) {
int min = Integer.MAX_VALUE;
int j = 1;
while (i - j * j >= 0) {
min = Math.min(min, memo[i - j * j]);
j++;
}
memo[i] = min + 1;
}
return memo[n];
}