课堂视频笔记-动态规划的集合理解

视频里的集合我就用 集合S[i,j]表示了 , 然后f(i,j)只是用来表示S[i,j]的某一个属性，也就是题目要求的属性。
S[i,j] 表示从0～i个物品里面挑选物品，物品重量不超过j的方案的集合。此时集合里的方案包含，在0~i位置的每一个物品, 都有“选”和“不选”的两种选择（这也是01背包的特点）。

所以S[i,j]可以分为选中第i个和不选中第i个的 两个部分 的合集。
为什么要这样分呢？因为这样更方便求f(i,j)。
f(i,j)为集合S[i,j]的函数，在这题里f(i, j)=Max(集合中方案的权重),即最大值。
如何对f(i, j) 求值呢？想办法推导出递推的公式。(参考斐波那契数列f(i) = f(i-1) + f(i - 2) 加f(0) = 0, f(1) = 1的base case）看能不能找到等式关系。
这个时候发现选i和不选i能够推导f(i,j)，所以S[i, j]集合就分成了选i和不选i的两部分。
分好后再按题目要求分别进行计算max，再联合两个部分（求两个部分max中的max），就能得到f(i,j)。

空间优化，为什么要用逆序？

先从两层看：第i层数据依赖第i-1层左上边的数据((i-1, j-v[i])循环j，就是左上边数据)), 所以更新第i层时第i-1层都必须已经算好。

压缩成一层：i-1层的压缩下来了，那对于某一个j，它左边的应该是i-1层压缩下来的。
如果按从左到右增序循环j, 那么左边的表示的都是i-1层数据被更新后的第i层数据了，此时公式变成了f(i,j) = f(i, j-v[i]) + w[i]。公式不符合f(i, j) = f(i-1, j-v[i] + w[i])。
所以不能更新左边，那就想从右边入手了。正好右边没有用到，也就是y总说的本题它不是找两头求中间的情况，所以让j递减循环。