种星星
0%

LeetCode题解|279. Perfect Squares

发表于 阅读次数： Valine：

题目链接：279. Perfect Squares

概述

本题目要求将一个给定的数n拆分为若干个平方数的和，求最小拆分数。

思路

这个题目可以用动态规划来做。

dp[i]代表组成i的最少平方数的个数，这个值最大就是它本身（看作都由1组成）。
而组成这个数的最小值要么就是本身，要么就是前面某一个数+一个平方数（所以看作值加上1）
所以状态转移方程为：dp[i] = min(dp[i - j * j] + 1, dp[i])（其中 j < sqrt(i）)
有转移方程后代码就很好写了。

这个题目还有另外一个解法，是四平方和定理（好吧，我没听过，读者有兴趣可以自己研究下）

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
    let dp = new Array(n + 1);
    for(let i = 0; i <= n; i++){
        dp[i] = n;
    }
    
    for(let i = 1; i <= n; i++){
        let sqrt = Math.floor(Math.sqrt(i));
        if(sqrt * sqrt == i){
            dp[i] = 1;
            continue;
        }
        dp[i] = n;
        for(let j = 1; j <= sqrt; j++){
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        }
    }
    return dp[n];
};

题解合集