二维dp数组可以转换成一维数组，不过要从后往前，是为了用到的都是上一层的。

416. 分割等和子集

与计数类的题目不同，这题dp的含义是bool值，使用下标为 i 及其前面的能否到达容量为 j。

class Solution {
public:
    // 非计数, 存放bool值
    // dp[i][j] 前i个能否把容量变成j
    // dp[i][j] = dp[i-1][j] || dp[i-1][j-[w[i]]]
    bool canPartition(vector<int>& nums) {
        int res = 0;
        for (const int &num : nums) res += num;
        if (res & 1) return false;
        res /= 2;
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(res + 1));
        // 物品
        for (int i = 0; i < n; i ++)
        {
            dp[i][0] = true;
            // 体积
            for (int j = 0; j <= res; j ++)
            {
                if (i > 0) dp[i][j] = dp[i-1][j];
                if (i > 0 && nums[i] <= j) dp[i][j] |= dp[i-1][j-nums[i]];
            }
        }

        for (int i = 0; i < n; i ++)
            if (dp[i][res])
                return true;
        return false;
    }
};