动态规划的一维优化问题

举个例子，0-1背包转移方程如下


dp数组第i行所依赖的其实都在第i-1行
故可以减去一维
关键思想在于如何实现dp[c] = max(dp[c],dp[c-v[i]]+w[i])
这里最大的问题是式子里，左边的代表第i行,右边的代表第i-1行，dp数组i-1行的值不能在使用之前被第i行的替换掉了，故选择从C->0的顺序遍历。需要确保dp[c-v[i]]存储的是上一行的值，即确保还没有被更新，所以遍历方向是从大到小即

 for (int i = 0; i < N; i++) {
            for (int j = C; j >= v[i]; j--) {
                // 不选该物品
                int n = dp[j]; 
                // 选择该物品
                int y = dp[j-v[i]] + w[i]; 
                dp[j] = Math.max(n, y);
            }
        }

完全背包的转移方程如下：

进行一维优化后的状态转移方程如下：

与0-1背包不同的是，右边最后一个式子是第i行的值，故要确保它已更新
故是从小到大遍历

for (int i = 0; i < N; i++) {
            for (int j = 0; j <= C; j++) {
                // 不考虑第 i 件物品的情况（选择 0 件物品 i）
                int n = dp[j];
                // 考虑第 i 件物品的情况
                int y = j - v[i] >= 0 ? dp[j - v[i]] + w[i] : 0; 
                dp[j] = Math.max(n, y);
            }
        }