LeetCode 279. 完全平方数

题目描述

给定一个正整数 n，你需要找到若干个完全平方数（比如 1, 4, 9, 16, ...），使得它们的和等于 n。你需要返回最少的完全平方数的个数。

示例 1:

输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4

示例 2:

输入: n = 13
输出: 2
解释: 13 = 4 + 9

Java 实现代码

java">class Solution {public int numSquares(int n) {// dp[i] 表示数字 i 需要的最少完全平方数的个数int[] dp = new int[n + 1];for (int i = 1; i <= n; i++) {dp[i] = Integer.MAX_VALUE; // 初始化为最大值for (int j = 1; j * j <= i; j++) {dp[i] = Math.min(dp[i], dp[i - j * j] + 1);}}return dp[n];}
}

解题思路

1. 动态规划：我们使用动态规划来解决这个问题，定义一个数组 dp，其中 dp[i] 表示数字 i 需要的最少完全平方数的个数。

2. 初始化：dp[0] = 0，因为数字 0 不需要任何完全平方数。

3. 状态转移：

   • 对于每个数字 i 从 1 到 n，我们遍历所有可能的完全平方数 j * j（其中 j 从 1 开始，直到 j * j 大于 i）。
   • 更新 dp[i] 为 Math.min(dp[i], dp[i - j * j] + 1)，表示使用一个完全平方数 j * j 后，剩下的部分 i - j * j 需要的最少完全平方数的个数加上 1。

4. 返回结果：最终返回 dp[n]，即为数字 n 需要的最少完全平方数的个数。

复杂度分析

• 时间复杂度：O(n * √n)，外层循环遍历 1 到 n，内层循环遍历所有小于等于 √n 的完全平方数。
• 空间复杂度：O(n)，需要一个大小为 n + 1 的数组 dp 来存储结果。

注：题目来源leetcode网站