思路

首先该题的数字可以重复使用，所以是一个完全背包问题。

动规五部曲

1.定义dp数组

dp[i]表示：和为 i的完全平方数的最少数量 。

2.递推公式

dp[j]=Math.min(dp[j-i*i]+1,dp[j]);

3.初始化

因为求的是最少的数量

dp[0]=0;其他元素要最大。

4.遍历顺序

可以先遍历物品也可以先遍历背包。其中i*i就是物品的价值。

5.打印dp数组

数组的最后一个元素如果不是初始值就是最后的结果，如果是的话，就返回-1.

代码

class Solution {    public int numSquares(int n) { int dp[] = new int[n+1]; dp[0]=0; for(int i = 1;i<=n;i++){     dp[i] =100000; } for(int i = 1;i<=n;i++){      for(int j=i*i;j<=n;j++){  dp[j]=Math.min(dp[j-i*i]+1,dp[j]);     } } if(dp[n] == 100000){     return -1; } return dp[n];    }}