关于维度的状态压缩常见于dp问题之中,在背包问题中,体积的枚举的顺序(从大到小or从小到大)是一个比较具有技巧的知识点。 我们知道,优化维数时一般都会将“第i个物品”这层状态优化掉。因此,在枚举第i层时,如果从小到大枚举,形如j-v[i]这类状态,当j增大到某一值时,就会使用j-v[i]来更新,而这时的j-v[i]属于第i层的更新,而我们的j应该由i-1层的j-v[i]更新,所以从大到小枚举j就可以避免以上的情况。