代码拉取完成,页面将自动刷新
同步操作将从 光花梗虎耳草/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...
)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 n
,返回和为 n
的完全平方数的 最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1
、4
、9
和 16
都是完全平方数,而 3
和 11
不是。
示例 1:
12
示例 2:
13
提示:
1 <= n <= 104
动态规划,定义 dp[i]
表示和为 i
的完全平方数的最少数量。
class Solution:
def numSquares(self, n: int) -> int:
dp = [0] * (n + 1)
for i in range(1, n + 1):
j, mi = 1, float('inf')
while j * j <= i:
mi = min(mi, dp[i - j * j])
j += 1
dp[i] = mi + 1
return dp[-1]
class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
for (int i = 1; i <= n; ++i) {
int mi = Integer.MAX_VALUE;
for (int j = 1; j * j <= i; ++j) {
mi = Math.min(mi, dp[i - j * j]);
}
dp[i] = mi + 1;
}
return dp[n];
}
}
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n + 1);
for (int i = 1; i <= n; ++i) {
int mi = 100000;
for (int j = 1; j * j <= i; ++j) {
mi = min(mi, dp[i - j * j]);
}
dp[i] = mi + 1;
}
return dp[n];
}
};
function numSquares(n: number): number {
let dp = new Array(n + 1).fill(0);
for (let i = 1; i <= n; ++i) {
let min = Infinity;
for (let j = 1; j * j <= i; ++j) {
min = Math.min(min, dp[i - j * j]);
}
dp[i] = min + 1;
}
return dp.pop();
}
func numSquares(n int) int {
dp := make([]int, n+1)
for i := 1; i <= n; i++ {
mi := 100000
for j := 1; j*j <= i; j++ {
mi = min(mi, dp[i-j*j])
}
dp[i] = mi + 1
}
return dp[n]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。