LeetCode 完全背包 279. 完全平方数

279. 完全平方数

给你一个整数 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 ，我们最大可以选择是数是 k=(int)sqrt(n)
题目转换过来就是从 1 到 k 之间选择任意个数（可以重复），使得其平方之和为 n ，求所有可能组合中最少需要多少个数字
这么一看题目就是完全背包问题了

我们定义 dp[ i ][ j ] 表示从 0 到 i 之间进行选择得到平方和为 j 的最少数字个数
对于任意 dp[ i ][ j ]，我们分为两种情况

1. 不能选择数字 i，i * i>j
   那么 dp[ i ][ j ]=dp[ i-1 ][ j ]
2. 可以选择数字 i，i * i<j
   那么答案是选择和不选择之间小的那个
   dp[ i ][ j ]=min(dp[ i-1 ][ j ]，dp[ i ][ j-i * i ]+1)

然后我们初始化 dp[ 1 ][ j ]
接着从 dp[ 1 ][ 0 ] 遍历数组即可
最后答案为 dp[ k ][ n ]

代码如下↓

class Solution {
public:
    int numSquares(int n) {
        int k=sqrt(n);
        vector<vector<int>> arr(k+1,vector<int>(n+1,0));
        for(int i=0;i<=n;i++)
        {
            arr[1][i]=i;
        }
        for(int i=2;i<=k;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i*i>j)
                {
                    arr[i][j]=arr[i-1][j];
                }
                else
                {
                    arr[i][j]=min(arr[i-1][j],arr[i][j-i*i]+1);
                }
            }
        }
        return arr[k][n];
    }
};

空间优化

根据 dp[ i ][ j ]=min(dp[ i-1 ][ j ]，dp[ i ][ j-i * i ]+1) 我么发现我们要求的值仅与上一行有关
那么不妨将它们都放到一行里
dp[ j ]=min(dp[ j ]，dp[ j-ii ]+1) （前面的dp[ j ]是dp[ i ][ j ]，后面的是dp[ i-1 ][ j ]，上一行的，dp[ j-ii ]是dp[ i ][ j-i*i ]）

对于我们要求的dp[ j ]，其与上一行的dp[ j ]和同一行的dp[ j-i*i ]有关
在求值的过程中，dp[ j ]就是上一行的值
而dp[ j-i * i ]，也就是前面的值需要是同一行的
那么我们正好顺序遍历，前面的值都是更新过的，这一行的值

代码如下↓

class Solution {
public:
    int numSquares(int n) {
        int k=sqrt(n);
        vector<int> arr(n+1,0x3f3f3f3f);
        arr[0]=0;
        for(int i=1;i<=k;i++)
        {
            for(int j=i*i;j<=n;j++)
            {
                arr[j]=min(arr[j],arr[j-i*i]+1);
            }
        }
        return arr[n];
    }
};