解释：01背包问题空间优化成一维数组，内循环逆序_背包问题,它优化成一维数组之后为什么倒着循环啊

〇、基本知识

01背包问题：
有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的空间是 Ci，得到的价值是 Wi。求解将哪些物品装入背包可使价值总和最大。

//dp[i][j]：前 i 件物品，放入容量为 j 的背包，获得的最大价值。
状态转移方程：dp[i][j] = max{dp[i - 1][j], dp[i - 1][j - C[i]] + W[i]}
1
2

//2维数组
public void pack2(int N, int V, int[] C, int[] W) {
    int[][] dp = new int[N + 1][V + 1];
    for (int i = 1; i <= N; i++) {
	    for (int j = 1; j <= V; j++) {
	        dp[i][j] = dp[i - 1][j];
	        if (j - C[i] >= 0) 
	        	dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - C[i]] + W[i]);
	    }
    }
}
1
2
3
4
5
6
7
8
9
10
11

一、必要的思考和理解：动态规划，其实是在 “有序填表”

既然你已经开始琢磨 “01背包问题 空间优化 一维数组 内循环逆序” 这个问题，相信以上的部分你已经基本理解了。

但是，你是否思考过这样一个问题：为什么二维数组 dp[i][j] 的 i 是从1~N，j 是从C[i]~V？不能是逆序吗，比如 i 从 N~1 不行吗？

其实，动态规划问题循环遍历过程，是一个 “有序填表” 的过程。既然是有序填表，循环遍历的顺序自然不能随便乱来。

接下来，我用一个具体的例子来说明：

//各参数具体数值如下：
int N = 5;
int V = 6;
int[] C = new int[]{0, 5, 1, 3, 2, 5};
int[] W = new int[]{0, 4, 3, 2, 1, 2};
1
2
3
4
5

循环结束，二维数组 dp[i][j] 长成这样：

从状态转移方程 ：

dp[i][j] = max{dp[i - 1][j], dp[i - 1][j - C[i]] + W[i]}
1

可以看出：要想得到 dp[i][j] 的值，必须得知道 dp[i-1][j] 和 dp[i-1][v-C[i]] 的值；

对应到 “填表” 上：要想填出第 i 行、第 j 列位置的数（即：dp[i][j]），我得知道 dp[i-1][j] 和 dp[i-1][v-C[i]] 位置上的数。

大家对应到上图，随便选择一个点 dp[i][j]，那么，dp[i-1][j] 就在 dp[i][j] 正上方的位置，而 dp[i-1][v-C[i]] 在 dp[i][j] 的左上方。

也就是说，当我们想填出 dp[i][j] 的数时，得确保其正上方的 dp[i-1][j] 和左上方的 dp[i-1][v-C[i]] 必须是填好的！

所以，先固定好 i，然后 j 从左往右填，然后 i++，这样，当前要填的位置的正上方和左上方都是填好的。至此，就解释了i、j 的遍历顺序。

理解了 动态规划，其实是在 “有序填表”，下面，开始探讨：为什么01背包问题优化空间复杂度变成一维数组后，代码内循环逆序？

三、解释 “一维数组时，内循环逆序”

//1维数组
void pack1(int N, int V, int[] C, int[] W) {
    int[] dp = new int[V + 1];
    for (int i = 1; i <= N; i++) {
        for (int j = V; j >= C[i]; j--) {  //发现内循环是逆序！！！
            dp[j] = Math.max(dp[j], dp[j - C[i]] + W[i]);
        }
    }
}
1
2
3
4
5
6
7
8
9

//dp[j]：前 i 件物品，放入容量为 j 的背包，获得的最大价值。
状态转移方程：dp[j] = max{dp[j], dp[j - C[i]] + W[i]}
1
2

光从状态转移方程看，感觉不就是把 [i] 省去了么，依然理解不了为什么逆序。

此时，我们需要结合具体例子，先不管顺序逆序的问题，首先理解一维数组到底是如何简化的（即：如何优化了空间复杂度）？

下面是不同的 i 下，当 j 遍历完时，数组 dp 的状态：

二维 dp 数组如下，方便上下对比：

可以清晰看到：一维数组每次就是把二维数组的第 i 行和第 i-1 行的数进行比较，把较大的数留下，“原地”形成新的一维数组。

理解了这点后，我们再去理解为什么内循环要逆序？即：为什么 j 从V~C[i]？为什么是 j--？

这时，我们需要借助刚才理解的一点：动态规划，其实是在 “有序填表”。

同样的，我们首先回顾此时的状态转移方程：

dp[j] = max{dp[j], dp[j - C[i]] + W[i]}
1

内循环逆序意味着：j 是从大数往小数走，对应填表的话，是从右往左填：

从之前的分析中我们得知：一维数组每次就是把二维数组的第 i 行和第 i-1 行的数进行比较。

这就意味着：dp[j] 和 dp[j - C[i]] 都必须得是第 i-1 轮的数！
如何理解这句话？
设想：现在 i 刚刚来到 3，此时一维 dp 数组里的数是 i = 2 时经过比较淘汰留下的数，所以此时 dp[j] 就是 i = 2 时的数，dp[j - C[i]] 仅仅是在 dp[j] 的左侧，自然也是 i = 2 时的数。

可是，如果是内循环顺序，也就是从左往右填的：

那么，我们就无法确保，dp[j] 左侧的 dp[j - C[i]]，是第 i-1 轮留下的数。

因为在第 i 轮，我们如果从左往右填的，那么 dp[j] 左侧的 dp[j - C[i]] 并不是第 i-1 轮的数，而是本轮（也就是第 i 轮）填的数。