动态规划 01背包问题 二维转一维过程及理解

1.  01背包：二维朴素写法

public static int getMaxValue(int[] weight, int[] values, int w) {

    int n = weight.length;
    int[][] dp = new int[n + 1][w + 1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= w; j++) {
            if (j >= weight[i - 1]) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + values[i - 1]);
            }
        }
    }

    return dp[n][w];
}

2.  01背包：二维朴素写法 —> 一维空间优化写法

public static int getMaxValue2(int[] weight, int[] values, int w) {
    int n = weight.length;

    int[] dp = new int[w + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = w; j >= weight[i-1]; j--) {
            if (j >= weight[i - 1]) {
                dp[j] = Math.max(dp[j], dp[j - weight[i - 1]] + values[i - 1]);
            }
        }
    }

    return dp[w];
}

3.  以上二维转一维 两个重点问题

3.1  为何可以用一维数组代替二维数组？

二维数组更新方式为

f[i][j] = f[i - 1][j] # 不含i的所有选法的最大价值
if j >= v[i]: # 判断含i的选法是否成立
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i])

可以看出f[i][:]只依赖于f[i-1][:]，所以根本没必要保留之前的f[i-2][:]等状态值；

使得空间从o(n*m)缩小到o(m)，n,m分别为物品个数和背包体积
其实每个物品的体积和价值在该层循环结束后也不会再用上，这里也可以压缩为两个o(1)的空间

3.2 、为何要逆序更新？

一维数组更新方式为

while j >= v[i]:
dp[j] = max(dp[j], dp[j - v[i]] + w[i])

我们只有上一层dp值的一维数组，更新dp值只能原地滚动更改；

注意到，

当我们更新索引值较大的dp值时，需要用到索引值较小的上一层dp值dp[j - v[i]]；
也就是说，在更新索引值较大的dp值之前，索引值较小的上一层dp值必须还在，还没被更新；
所以只能索引从大到小更新。

看这段话是不是理解起来比较难，那我们 模拟一遍  逆序的过程  一切疑问皆明了