青岛手机网站制作系统推广公司
2024 7/7 转眼间就到周日啦！昨天下午开组会，开了三个半小时。如坐针毡，会后跑了个步、洗了个澡、洗了衣服、躺床上看了会《罪与罚》，睡着了。早上起来，去拿我昨晚充电的车，当我看到车没有停在昨天的位置，我就知道不妙了，是的，被拔了，世上总有这种低素质人群，可能是基因里带的坏。天气除了热，景色还是不错的，附两张图
图1、南校区视角
图2、图片左边是一只蝴蝶，本来是两只的
okok，做题啦
1、题目描述
2、算法分析
给一个整数n，要求返回和为n的完全平方数的最少数量。
测试用例有两个，分别为12、13。根据测试案例以及面向对象思想，我编写出了以下代码：
public int numSquares(int n) {if(n == 12){return 3;}if(n == 13){return 2;}return 0;}
很显然，通过案例，但是提交出错了，那么我们得想出一种合适的算法来求解。题目可以分解为：
求完全平方数；
下一步就是如何求和为n的完全平方数的最少数量了；
这一步怎么写出来呢？
我的方案就是：
看题解。
题解给出的也是dp思想，大致思路：
算法思路如下：
- 定义状态：我们定义一个数组
dp，其中dp[i]表示将整数i表示为完全平方数之和的最少个数。 - 初始化状态：对于
dp[0]，由于0不需要任何平方数来表示，所以dp[0] = 0。 - 状态转移方程：对于每个
i（从1到n），我们遍历所有可能的平方数j*j（其中j*j <= i）。对于每个这样的平方数，我们检查dp[i - j*j]的值，即表示i - j*j为平方数之和的最少个数。然后，我们更新dp[i]为所有可能的
dp[i - j * j] + 1中的最小值（其中+1是因为我们加上了当前的平方数j*j）。这样，我们就得到了将i表示为平方数之和的最少个数。 - 计算结果：最终，
dp[n]将包含将n表示为平方数之和的最少个数，这就是我们要找的答案。
3、代码
public int numSquares(int n) {// 创建一个长度为 n+1 的数组 dp，用于存储从 0 到 n 每个数表示为平方数之和的最少个数int[] dp = new int [n + 1];// 遍历从1到n的每个数 for(int i = 1; i <= n; i++){// 初始化minN为最大值，用于寻找最小的平方数组合数量 int minN = Integer.MAX_VALUE;// 遍历所有可能的平方数j*j（其中j*j小于等于i）for(int j = 1; j * j <= i; j++){// 如果dp[i - j * j]存在且小于minN，则更新minN为dp[i - j * j] // 这意味着我们可以通过将i拆分为j*j和i-j*j，并找到i-j*j的最少平方数组合数量来优化i的组合数量 minN = Math.min(minN, dp[i - j * j]);}// 更新dp[i]为将i表示为平方数之和的最少个数，即minN+1（因为我们要加上当前的平方数j*j）dp[i] = minN + 1;}// 返回dp[n]，即将n表示为平方数之和的最少个数return dp[n];}
4、复杂度分析
- 时间复杂度： O ( n n ) O(n\sqrt{n}) O(nn)。其中 n 为给定的正整数。状态转移方程的时间复杂度为 O ( n ) O(\sqrt{n}) O(n)。共需要计算 n
个状态，因此总时间复杂度为 O ( n n ) O(n\sqrt{n}) O(nn)。 - 空间复杂度： O ( n ) O(n) O(n)。我们需要 O(n) 的空间保存状态。
okok，写完啦，在IDE上打断点debug后也是对其加深理解了，再见，坐等外卖啦！