熟悉动态规划的童鞋都知道，dp的状态方程通常都是二维数组及以上。我们总将其定义为dp[N][C]，例如int dp[N][C]，N=10^6，C=10^6，此时空间消耗为4*N*C=4×10^12，很大可能超过比赛中题目对空间的限制。那么我们是否可以优化它呢？
拿背包问题举例，我们通常将行范围定为物品个数，每处理当前物品只需在前一个物品基础上改变，所以每一轮需要处理的数组行数只有i和i-1这两行，这样我们便可以引申出“滚动数组”，只需要不断交替dp[0][]和dp[1][]就可以处理完N个物品。
如上图，处理物品的过程
①第1个物品：0->1；第2个物品：1->2；第3个物品：2->3；第4个物品：3->4；
②第1个物品：0->1；第2个物品：1->0；第3个物品：0->1；第4个物品：1->0；
如此一来，空间复杂度便会由O(NC)优化为O(C）
标签：10,滚动,处理,数组,物品,动态,dp From： https://blog.csdn.net/weixin_73296216/article/details/137519189