复制
给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.
递归对内存的要求也很高, 如果数字非常大,也会面临爆栈的风险,将递归转化为循环可以解决。
复制 const mapper = {};
function d (n , level) {
if (n === 0 ) return level;
let i = 1 ;
const arr = [];
while (n - i * i >= 0 ) {
const hit = mapper[n - i * i];
if (hit) {
arr .push (hit + level);
} else {
const depth = d (n - i * i , level + 1 ) - level;
mapper[n - i * i] = depth;
arr .push (depth + level);
}
i ++ ;
}
return Math .min ( ... arr);
}
/**
* @param {number} n
* @return {number}
*/
var numSquares = function (n) {
return d (n , 0 );
};
复制 for ( let i = 1 ; i <= n; i ++ ) {
for ( let j = 1 ; j * j <= i; j ++ ) {
// 不选(dp[i]) 还是 选(dp[i - j * j])
dp[i] = Math .min (dp[i] , dp[i - j * j] + 1 );
}
}
复制 class Solution {
public:
int numSquares(int n) {
static vector<int> dp{0};
while (dp.size() <= n) {
int m = dp.size(), minVal = INT_MAX;
for (int i = 1; i * i <= m; ++i) minVal = min(minVal, 1 + dp[m - i * i]);
dp.push_back(minVal);
}
return dp[n];
}
};
复制 /**
* @param {number} n
* @return {number}
*/
var numSquares = function (n) {
if (n <= 0 ) {
return 0 ;
}
const dp = Array (n + 1 ) .fill ( Number .MAX_VALUE);
dp[ 0 ] = 0 ;
for ( let i = 1 ; i <= n; i ++ ) {
for ( let j = 1 ; j * j <= i; j ++ ) {
// 不选(dp[i]) 还是 选(dp[i - j * j])
dp[i] = Math .min (dp[i] , dp[i - j * j] + 1 );
}
}
return dp[n];
};