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

Idea

对于任何一个正整数n
我们可以把它表示成这样的形式.
设dp[n]为n的完全平方数最少之和
那么有递推公式dp[n]=1+dp[b]
而初始条件
dp[0]=0;
dp[1]=1;
由此 我们可以得到动态规划代码

    public static int numSquares(int n) {
        int[] dp=new int[n+1];
        for(int i=1;i<=n;i++)
        {
            dp[i]=Integer.MAX_VALUE;
        }
        dp[0]=0;
        dp[1]=1;
        for(int i=1;i<=n;i++)
            for(int j=1;i-j*j>=0;j++)
            {
                dp[i]=Math.min(dp[i],dp[i-j*j]+1);
            }
        return dp[n];
    }