LeetCode 279. 完全平方数
题目描述
思路分析
这个问题是一个经典的动态规划问题，通常使用动态规划来解决。
我们可以定义一个一维数组
dp，其中dp[i]表示和为i的完全平方数的最少数量。初始时，我们可以将
dp数组的所有元素都设置为一个较大的数，然后逐步计算每个和的最少数量。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func numSquares(n int) int {
dp := make([]int, n+1) // dp[i] 表示和为 i 的完全平方数的最少数量
for i := 1; i <= n; i++ {
dp[i] = math.MaxInt
}
for i := 1; i <= n; i++ {
j := 1
for j*j <= i {
dp[i] = min(dp[i], dp[i-j*j]+1)
j++
}
}
return dp[n]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
1
write your code here
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！