你实际上的方程应该是
$$
f(i,j)=\sum_{k=0}^{\min\{a_i,j\}}f(i-1,j-k)
$$
对吧
那你要体现出你在对后面那个式子求和,是不是就应该写
```
for(int k=0;k<=min(a[i],j);k++) s+=f[i-1][j-k];
f[i][j]=s;
```
然后你意识到根本不需要一个中间变量来保存求和结果,所以你把上面出现`s`的地方全部换成`f[i][j]`
```
for(int k=0;k<=min(a[i],j);k++) f[i][j]+=f[i-1][j-k];
```
加上取膜是不是就是后面那个
by konjacq @ 2021-03-19 10:02:21
1. 在你的代码中,对于若干个不同 $k$,对 $f_{i,j}$ 不断覆盖,也就是你转移到最后 $f_{i,j} = f_{i-1,j}+f_{i-1,j-\min(j,a_i)}$。
2. 你想考虑的是选不选的情况,然而由于 $k \in [0, \min(j, a_i)]$,那么已经将不选与选若干个的情况都考虑进去了,于是转移就是对 $f_{i-1,j-k}$ 求和。
3. 实际上这个 $f_{i,j}$ 表示的是**方案数**而不是**最佳方案数**。
by daklqw @ 2021-03-19 10:04:56
你的想法是:我这一步的值就等于上一步的选,和不选的方案数的总和。可是,由于你的等式是等于号,而不是+=,因此你的dp[i][j]实际上取到的是最后一次循环的值,你的这一次次循环实际上不是累加,而是一直在覆盖着赋值,所以你的dp[i][j]=dp[i-1][m]+dp[i-1][j-a[i]],因此你的代码处理结果实际与你的想法大相径庭。
------------
那么怎么解决?其实你的代码还有一个错误:那就是k取0的时候,实际上已经算是不取了,所以你没必要分类讨论,也就可以把dp[i-1][j]给去掉了。再加上我们上面说,循环应当是一次次的累加,所以改良后的代码应当是dp[i][j]+=dp[i-1][j-k],这是不是就与答案一致了?
by Calanosay @ 2021-04-02 16:10:12