01背包中的常数优化
基础01背包
最基础的01背包问题：一个背包的容量为V，现有N个物品，每个物品都具有一个体积$C_i$和重量$W_i$，把这些物品装入背包，求背包能下物品的最大重量。
通过动态规划求解此题，设数组$dp [N+1][V+1]$， $dp[i][j]$代表使用前i个物品放入体积为j的背包的最大重量。
现在有状态转移方程：
即在不使用第i个物品和使用第i个物品中取最大值。使用二重循环更新此方程，即i从1到N，j从$C_i$到V
空间压缩
观察上面的状态转移方程，$dp[i][j]$依赖于二位数组中上一行的$dp[i-1][j] $和$d[i-1][j-C_i]$，且一个在正上方一个在左上方，因此求dp数组第i行的值时，只需要dp数组i-1行的值，因此只需要一维的dp数组$dp[V+1]$，就可以实现迭代更新。
此时状态转移方程为：
不过为了保证在更新dp[j]时，$dp[j - Ci]$对应的是$i-1$个物品放入容量为$j-C_i$的最大值，第二层循环需要逆序更新。即j从V到$C_i$，正序更新的话，由于$j - C_i$小于$j$,在更新dp[j]的时候,$dp[j - Ci]$已经被更新过了，对应着$i$个物品放入容量为$j-C_i$的最大值，与状态转移方程的含义不符。
常数优化
在《背包九讲》这一篇文章中，提到还可以常数级别优化。即第二层循环逆序更新时，j从V减少到$max(V - \sum_{idx=i+1}^NC_{idx},C_i)$
推导如下：
设$\sum_{idx=i+1}^NC_{idx}$为key，为什么当V - key大于$C_i$时，j的值只用从V减少到V-key即可。而不用减少到$C_i$呢？
$V - key \ge C_i$这个不等式意味着，背包能装下$C_i$和它后面的所有物品，当j从V减少到V-key时，剩下的体积刚好还能装下$C_i$这个物品，此时就不需要再减少了，再减少就放不下$C_i$这个物品了，只能放弃更新左边的值，继续沿用上一行的dp数组值。