本题是递推。不懂的自行百度查阅。
1
本题是递推。不懂的自行百度查阅。
2
 
3
群里也有递推的ppt。
4
 
5
我们定义d[i][j]为处理完`1^2,2^2，……,i^2`后值为j的所有情况。即`j=k0*0^2+k1*1^2+……ki*i^2`。
6
`dp[1][4]`的意思就是值为`4`，最大的底数为`1`。`4=1^2+1^2+1^2+1^2`.只有一种情况。
7
而`dp[2][4]`的意思便是 `4=1^2+1^2+1^2+1^2=2^2` 可以有两种情况。即i为底数最大的情况。
8
 
9
`d[i][j]=d[i-1][j]+d[i][j-i*i]`;
10
 
11
`dp[1][5]=dp[1][4]+dp[0][5]`;
12
这句的意思就是已知`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`种。
13
 
14
当`j<i*i,d[i][j]=d[i-1][j]`。
15
 
16
`dp[3][5]=dp[2][5]`
17
即不取$3^{2}$项.
18
 
19
不理解的自己模拟操作。`dp[0][0]=1`，我们知道0=k0*0^2是可以的。
20
`MAXi=31`是因为`1000`最大可取的项是$32^{2}$。再大计算下去没意义。
21
 
22
题目略有难度,大家可以先练习其他递推题目熟练算法。
23
 
24
（Ps：以后递推类型题目题解基本以递推式形式给出。）
25
 
26
 
27
 
28
 
29