echo

任生命穿梭 时间的角落

0%

完全平方数

Posted on In Valine:

279. 完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

动态转移方程为：dp[i] = MIN(dp[i], dp[i - j * j] + 1)，i表示当前数字，j*j表示平方数。

示例 1:

1
2
3
输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.

示例 2:

1
2
3
输入: n = 13
输出: 2
解释: 13 = 4 + 9.

使用 dp 数组来保存以当前下标为和的完全平方数的个数。依次对每个数判断是否可以使用之前的dp数组中的值加一个较大的完全平方数得到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        for(int i=1; i<=n; ++i){
            //最坏的情况，全部由 1 相加得到
            dp[i] = i;
            for(int j=1; i-j*j>=0; ++j){
                //尝试由 i-1, i-4, i-9 ...得到 i 
                dp[i] = Math.min(dp[i], dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
}

时间复杂度为O(n*sqrt(n))，空间复杂度为 O(n)。