本题是递推。不懂的自行百度查阅。 群里也有递推的ppt。 我们定义d[i][j]为处理完`1^2,2^2，……,i^2`后值为j的所有情况。即`j=k0*0^2+k1*1^2+……ki*i^2`。 `dp[1][4]`的意思就是值为`4`，最大的底数为`1`。`4=1^2+1^2+1^2+1^2`.只有一种情况。 而`dp[2][4]`的意思便是 `4=1^2+1^2+1^2+1^2=2^2` 可以有两种情况。即i为底数最大的情况。 `d[i][j]=d[i-1][j]+d[i][j-i*i]`; `dp[1][5]=dp[1][4]+dp[0][5]`; 这句的意思就是已知`dp[1][4]`和`dp[0][5]`的种类,`dp[1][4]`为有1种情况，那么就是这样：`5=（1^2+1^2+1^2+1^2）+1^2`，或者说我们`dp[0][5]` 那么就是`5=k0*0^2`。不可能存在这种情况，所以`dp[0][5]=0`。我们得到了`dp[1][5]`的情况只有`1`种。 当`j<i*i,d[i][j]=d[i-1][j]`。 `dp[3][5]=dp[2][5]` 即不取$3^{2}$项. 不理解的自己模拟操作。`dp[0][0]=1`，我们知道0=k0*0^2是可以的。 `MAXi=31`是因为`1000`最大可取的项是$32^{2}$。再大计算下去没意义。 题目略有难度,大家可以先练习其他递推题目熟练算法。 （Ps：以后递推类型题目题解基本以递推式形式给出。）