首相我们要了解dp问题的本质 其实dp就是一个递推过程 在初始化最开始的情况后 就可以一直递推下去进而得到我们想要的结果;
举个例子 01背包问题求最大价值问题 我们没有进行初始化
即f[0][0]=0; 状态转移方程
f[i][j]=f[i-1][j];
if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
求最大值 所以当然要有max
求最大价值 所以方程在递推的时候肯定要出现价值w[i]
那么在(0,0)之后的所有方案都可以经过这样的初始化和状态转移方程计算max
eg f[1][1];f[1][2];f[1][3] 都会基于f[0][0]=1 进而得出结果为0
而在在背包问题求方案数事 初始化f[0][0]=1 状态转移方程为
f[i][j]=f[i-1][j];
if(j>=v[i) f[i][j]+=f[i-1][j-v[i]];
求方案数 所以对于集合的划分出来的子集 我们都要进行补充不漏的做加法
同理在(0,0)之后的所有方案都可以经过这样的初始化和状态转移方程计算count
eg f[1][1],f[1][2],f[1][3] 都会基于f[0][0]=1 进而得出结果为1;