做网站数据库设计,上海外贸网站设计,手机版网站如何建设,手机端网站建设教程视频教程279. 完全平方数 文章目录 [279. 完全平方数](https://leetcode.cn/problems/perfect-squares/)一、题目二、题解方法一#xff1a;完全背包二维数组方法二#xff1a;一维数组#xff08;空间复杂度更小的改进版本,最下面的两个版本不需要存储完全平方数#xff09; 一、题…279. 完全平方数 文章目录 [279. 完全平方数](https://leetcode.cn/problems/perfect-squares/)一、题目二、题解方法一完全背包二维数组方法二一维数组空间复杂度更小的改进版本,最下面的两个版本不需要存储完全平方数 一、题目
给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。
示例 1
输入n 12
输出3
解释12 4 4 4示例 2
输入n 13
输出2
解释13 4 9提示
1 n 104
二、题解
方法一完全背包二维数组
算法思路
这道题要求找到和为n的完全平方数的最少数量下面是解题思路的详细说明 首先我们需要找到比n小的最大完全平方数这个完全平方数不会大于n。我们可以通过遍历从1开始的完全平方数来找到这个数。在代码中这部分的逻辑是 int target 0;
int i 1;
for(i 1; i n; i){if(i * i n){break;}
}
target i - 1;这里的target就是比n小的最大完全平方数。 接下来我们建立一个二维动态规划数组dp其中dp[i][j]表示使用前i个完全平方数组成和为j的最少数量。 我们初始化dp[1][i]为i因为只能使用一个完全平方数1所以组成任意数字j的最少数量都是j本身。 接下来我们开始填充dp数组的其余部分。我们从2号完全平方数开始遍历完全平方数的个数从2到target然后遍历组成的和从0到n。在每个位置(i, j)我们有两个选项 保持dp[i][j]不变这意味着我们不使用当前的完全平方数i所以最少数量与前一个状态dp[i-1][j]相同。尝试使用当前的完全平方数i如果可以的话将dp[i][j]更新为dp[i][j-i*i]1这表示使用了一个完全平方数i所以数量加一。 最终dp[target][n]就是答案即使用前target个完全平方数组成和为n的最少数量。
具体实现
下面是具体的代码实现已经按照上述思路注释
class Solution {
public:int numSquares(int n) {// 寻找离n最接近的完全平方数int target 0;int i 1;for(i 1; i n; i){if(i * i n){break;}}target i - 1;// 建立dp数组dp数组的含义是使用前i个完全平方数组成和为j的最少数量vectorvectorint dp(target1, vectorint(n1, INT_MAX));// 初始化dp数组使用一个完全平方数1组成任意数字j的最少数量都是j本身for(int i 0; i n; i){dp[1][i] i;}// 填充dp数组for(int i 2; i target; i){for(int j 0; j n; j){dp[i][j] dp[i-1][j]; // 不使用当前完全平方数iif(j i * i dp[i][j-i*i] ! INT_MAX){dp[i][j] min(dp[i][j], dp[i][j-i*i]1); // 使用当前完全平方数i}}}return dp[target][n];}
};算法分析
时间复杂度遍历完全平方数1到target需要O(target)的时间填充dp数组需要O(target * n)的时间。所以总时间复杂度是O(target * n)。空间复杂度使用了一个二维dp数组大小为(target1) * (n1)所以空间复杂度是O(target * n)。
方法二一维数组空间复杂度更小的改进版本,最下面的两个版本不需要存储完全平方数
class Solution {
public:int numSquares(int n) {// 建立dp数组dp[i]表示凑成i所需要的最少完全平方数的个数vectorint dp(n 1, INT_MAX);dp[0] 0;// 计算完全平方数列表vectorint squares;for (int i 1; i * i n; i) {squares.push_back(i * i);}for (int i 1; i n; i) {for (int square : squares) {if (i square) break; // 如果当前数小于完全平方数则跳出循环dp[i] min(dp[i], dp[i - square] 1);}}return dp[n];}
};
class Solution {
public:int numSquares(int n) {vectorint dp(n 1, INT_MAX);dp[0] 0;for (int i 0; i n; i) { // 遍历背包for (int j 1; j * j i; j) { // 遍历物品dp[i] min(dp[i - j * j] 1, dp[i]);}}return dp[n];}
};class Solution {
public:int numSquares(int n) {vectorint dp(n 1, INT_MAX);dp[0] 0;for (int i 1; i * i n; i) { // 遍历物品for (int j i * i; j n; j) { // 遍历背包dp[j] min(dp[j - i * i] 1, dp[j]);}}return dp[n];}
};
