leetcode刷题(第279题)——完全平方数
一、题目描述
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等 于 n。你需要让组成和的完全平方数的个数最少。 给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数 自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
二、示例
输入：n = 12 输出：3 解释：12 = 4 + 4 + 4
三、解析
这题采用的方法是动态规划，动态规划的递归公式是dp[i] = Math.min(dp[i], dp[i - j * j] + 1),并且在起始时，dp[i] 永远都是等于 i的。
四、代码
/**
* @param {number} n
* @return {number}
*/
var numSquares = function(n) {
let dp = new Array(n + 1).fill(0)
for(let i = 1; i < dp.length; i++) {
dp[i] = i
for(let j = 1; i - j * j >= 0; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1)
}
}
return dp[n]
};
五、复杂度分析
时间复杂度为O(n* sqrt(n)),空间复杂度为O(n)
下一篇：
算法积累-跳台阶问题