LeetCode 279. 完全平方数

题目描述

✅ 279. 完全平方数

image-20250420115115388

image-20250510232523413

思路分析

这道题的本质是完全背包问题，目标是用最少的完全平方数凑出目标 n。

设 dp[i] 表示组成数字 i 所需的最少完全平方数的数量。

image-20250510233229558

image-20250510232721859

参考代码



1
2
3
4
5
6
7
8
9
10
11
12
13



func numSquares(n int) int {
	dp := make([]int, n+1) // dp[i] 表示组成 i 的最少完全平方数的个数
	dp[0] = 0

	for i := 1; i <= n; i++ {
		dp[i] = n
		for j := 1; j*j <= i; j++ {
			dp[i] = min(dp[i], dp[i-j*j]+1)
		}
	}

	return dp[n]
}

➡️ 点击查看 Java 题解



1



write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2025/70176092
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！