经典动态规划：分割类题型——01（LC279）

题目：给定一个正整数，求其最少可以由几个完全平方数相加构成。

输入是给定的正整数，输出也是一个正整数，表示输入的数字最少可以由几个完全平方数相
加构成。

题解：

首先初始化长度为 n+1 的数组 dp，每个位置都为 0
如果 n 为 0，则结果为 0
对数组进行遍历，下标为 i，每次都将当前数字先更新为最大的结果，即 dp[i]=i，比如 i=4，最坏结果为 4=1+1+1+1 即为 4 个数字
动态转移方程为：dp[i] = MIN(dp[i], dp[i - j * j] + 1)，i 表示当前数字，j*j 表示平方数
时间复杂度：O(n*sqrt(n))O(n∗sqrt(n))，sqrt 为平方根

class Solution {
    public int numSquares(int n) {
    int []dp=new int[n+1];//初始化都为0
    for(int i=1;i<=n;i++){//循环数组的值
        dp[i]=i;//最坏的情况是都只+1
        for(int j=1;i-j*j>=0;j++){//这里是寻找j的平方数
            dp[i]=Math.min(dp[i],dp[i-j*j]+1);//选取2个数最小的值，选后者就给后者+1
        }
    }
    return dp[n];
    }
}