动态规划：二维数组降维技巧

主要思考两个问题：

1. dp[i][j]这个位置的值跟哪些数据有关；
2. 二维数组降维去掉哪一维

举个例子，对于0-1背包问题

我们记dp[i][j]为前i个物品放入一个容量为j的背包可以获得的最大价值；确定上述两个问题：

1. dp[i][j]这个位置的值跟dp[i-1][j-w[i]]和dp[i-1][j]有关；其状态转移方程为：

   dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

2. 去掉哪一维，我们通过状态转移方程可以看到，后者的max里面的第一维是不变的，也就是说dp[i][j]跟前i-1个物品的最大价值有关，因此我们尝试去掉第一维，保留j，则状态转移方程就为：

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

在确定了这两个问题之后，我们就需要确定dp[i]的定义了，在0-1背包问题上，dp[i]的定义应该为：

在当前物品数量的情况下，放入一个容量为i的背包可以获得的最大价值；

其实这里的状态转移方程的思想跟不定义中间变量交换两个变量的值的思想是一样的：

public void swap(int[] a, int i, int j) {
    a[i] += a[j];
    a[j] = a[i] - a[j];
    a[i] -= a[j];
}

0-1背包问题的核心代码如下：

for(int i=1; i<=N; i++) {
    for( int j=C; j>=1; j--) {
        if(j > w[i]) {
            dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
            continue;
        }
        break;
    }
}

将其进行降维优化后，其实在外层i遍历完成之后，dp[j]就已经保存了前i个物品放入容量为j的背包的最大价值了，因此在进行下一次i+1遍历的时候可以所有的dp[j]都是原来二维数组中的dp[i][j]的值：

for(int i=1; i<=N; i++) {
    for( int j=C; j>=1; j--) {
        if(j > w[i]) {
            dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]);
            continue;
        }
        break;
    }
}