LeetCode 279 完全平方数

给你一个整数 n ，返回和为 n 的完全平方数的最少数量。

完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例：

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

动态规划

将问题转化为完全背包问题，那么此处背包的容量就是 n ，并没有给定相应的物品，但是要将背包 n 装满，那么使用的物品就应该是 1-n 中的全部完全平方数，首先创建物品数组。

vector<int> nums;
for(int i=1;i*i<=n;i++){
    nums.push_back(i*i);
}

那么此处的物品数组就是 nums ，在物品数组中选取物品将背包装满，要求使用的物品数量能少。那么此处的处理方式就是和322.零钱兑换完全相同。此处求解的是最少的完全平方数的个数，不存在组合和排列的问题，因此既可以先遍历背包也可以先遍历物品。

动态规划数组的定义：定义数组 dp[n+1] 表示总和为 n 的最少的完全平方数的数量
动态规划数组的推导：在第 i 次迭代中，考虑元素 nums[i] ，尝试使用 nums[i] 来减少数量 dp[j]=min(dp[j],dp[j-nums[i]]+1) （此处需要判断 dp[j-nums[i]]!=INT_MAX）
动态规划数组的初始化：对于 dp[0] 实际是不符合问题的定义，为了满足后续的计算，将其初始化为 dp[0]=0 ，对于其他元素，由于递推方式为 dp[j]=min(dp[j],dp[j-nums[i]]+1) 那么对于初始不能恰好装满的容量，都初始化为 INT_MAX 。
动态规划数组的遍历顺序：此处先遍历物品再遍历背包，并且都采用从前向后的遍历方式。
举例验证：n=13

dp={0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13}
dp={0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4}
dp={0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3, 2}

代码实现：

class Solution {
public:
    int numSquares(int n) {
        vector<int> nums;
        for(int i=1;i*i<=n;i++){
            nums.push_back(i*i);
        }
        vector<int> dp(n+1,INT_MAX);
        dp[0]=0;
        for(int i=0;i<nums.size();i++){
            for(int j=nums[i];j<=n;j++){
                if(dp[j-nums[i]]!=INT_MAX){
                    dp[j]=min(dp[j],dp[j-nums[i]]+1);
                }
            }
        }
        return dp[n];
    }
};

此处的空间复杂度可优化，对于物品数组是可以不存储的：

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1,INT_MAX);
        dp[0]=0;
        for(int i=1;i*i<=n;i++){
            for(int j=i*i;j<=n;j++){
                if(dp[j-i*i]!=INT_MAX){
                    dp[j]=min(dp[j],dp[j-i*i]+1);
                }
            }
        }
        return dp[n];
    }
};

Mark's blogs

LeetCode-279-完全平方数

LeetCode 279 完全平方数

动态规划