给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 n ,返回和为 n 的完全平方数的 最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。
示例 1:
输入:n =12输出:3 解释:12 = 4 + 4 + 4
示例 2:
输入:n =13输出:2 解释:13 = 4 + 9
提示:
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 }