LeetCode 279. 完全平方数
题目描述
给定一个正整数 n，你需要找到若干个完全平方数（比如 1, 4, 9, 16, ...），使得它们的和等于 n。你需要返回最少的完全平方数的个数。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4
示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9
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];}
}
解题思路
动态规划：我们使用动态规划来解决这个问题，定义一个数组
dp，其中dp[i]表示数字i需要的最少完全平方数的个数。初始化：
dp[0] = 0，因为数字0不需要任何完全平方数。状态转移：
- 对于每个数字
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。返回结果：最终返回
dp[n]，即为数字n需要的最少完全平方数的个数。
复杂度分析
- 时间复杂度：O(n * √n)，外层循环遍历
1到n，内层循环遍历所有小于等于√n的完全平方数。- 空间复杂度：O(n)，需要一个大小为
n + 1的数组dp来存储结果。
注：题目来源leetcode网站
