416-状态压缩

哈喽 ~

你好啊 ~ 我是蓝莓 ~

LeetCode 416 （状态压缩）

在上一篇文章中，提到了怎么使用 动态规划 的方法来解决这个问题，但其实还能够进一步对改问题做优化。

在更新 dp 数组的时候，更新 第i号 行的值需要使用到 第i-1号 行的数据才可以，而更新完成 第i号 行后，就不会再次用到 第i-1号 行的数据了，所以并不需要存储那么多的值，我们可以把 二维 的 dp 数组压缩成 一维 的 dp 数组。

定义 dp 数组

bool dp[C]

修改状态转移方程

在之前的状态转移方程式这样的：

dp[i][j]

= dp[i-1][j-nums[i]] || dp[i-1][j]

使用了一维的 dp 数组后：

dp[j] = dp[j-nums[i]] || dp[j]

你仔细想想，相信这个式子是非常好理解的 ~ 等号右边的 dp[j] 可以理解为旧的 dp[j]，它就相当于 dp[i-1][j]。等号左边的 dp[j] 是新一轮的 dp[j] 其实就相当于 dp[i][j]，但是为什么能够直接把新的 dp[j] 放在旧的 dp[j] 的位置呢？因为旧的 dp[j] 的值最后一次使用就是在计算新的 dp[j] 的时候，而此后再也不会被用到了。

这里所说到的最后一次使用是按照新的计算顺序而言的，下边就会说明新的计算顺序是怎样的。

如何更新 dp 数组

在更新一维 dp 数组的时候就不能像二维那样的顺序来更新了，因为新的 dp[j] 的值取决于旧的dp[j] 和 dp[j-nums[i]] 如果更新 dp 数组是按照从左到右进行更新的话，计算靠右的值需要用到左边的值，而左边是先被更新的，所以就已经被覆盖了。

那么很简单的，我们只需要按照从右到左的顺序进行计算并且更新一维的 dp 数组就可以了

到这里思考一下，为什么这种优化方式叫做 状态压缩 呢，相信聪明的你也看出来了，dp 数组占用的空间少了很多，少存了很多的中间状态的值。少了就是压缩了嘛 ~

完整版代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int num : nums)
            sum += num;

        // sum 是奇数的时候是不可能分割的
        if(sum % 2 != 0) return false;

        // [0...nums.size()-1] 数值
        // [0...C] 容量
        int C = sum / 2;

        // 容量 [0...C]
        int dp[C+1];

        // 处理仅考虑 0 号元素的情况
        dp[0] = true; // 选择不装 0 号元素可装满
        for(int j = 1 ; j <= C ; ++j)
            dp[j] = false;
        // 该位置可装满
        if(nums[0] <= C) dp[nums[0]] = true;

        for(int i = 1 ; i < nums.size() ; ++i) {
            for(int j = C ; j >= 0 ; --j) {
                // 没办法装入 i 号元素的时候
                // dp[j] 的值不变
                if(j >= nums[i]) {
                    dp[j] = dp[j] || dp[j-nums[i]];
                }
            }
        }

        return dp[C];
    }

};