279. 完全平方数(leetcode)

LXL's Blog / 2024-09-04 / 原文

https://leetcode.cn/problems/perfect-squares/description/

简单完全背包,需要注意的是由于求的是最小,因此初始化时需要把初始层f[0]全置为无穷大,用于保证一定能计算出min
具体可以看灵神的解释

递归边界：dfs(0,0)=0，因为没有数可以选了，且要得到的数等于 0，那么答案为 0。
如果 j>0，那么 dfs(0,j)=∞，这里用 ∞ 表示不合法的状态，从而保证上式中的 min 取到合法的状态。
注意本题是一定有解的，因为 1 是完全平方数。

作者：灵茶山艾府
链接：https://leetcode.cn/problems/perfect-squares/solutions/2830762/dong-tai-gui-hua-cong-ji-yi-hua-sou-suo-3kz1g/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public int numSquares(int n) {
        // f[i][j]表示前i个数中选,体积等于j的选的数最少得数量
        // 以第i个数选多少来划分子集
        // f[i][j]=min(f[i-1][j],f[i][j-nums[i]]);
        int[][] f=new int[110][10010];
        Arrays.fill(f[0],Integer.MAX_VALUE);
        f[0][0]=0;
        int res=Integer.MAX_VALUE;
        for(int i=1;i*i<=n;i++) // i*i一定不超过总和n
            for(int j=0;j<=n;j++)
            {
                if(j>=i*i)f[i][j]=Math.min(f[i-1][j],f[i][j-i*i]+1);
                else f[i][j]=f[i-1][j];
            }
        // 由于i*i<=n,因此i最大为sqrt(n)
        return f[(int)Math.sqrt(n)][n];
    }
}