2023.8.12

         太难了ToT.... 一题做了一个下午。

        本题是动规题目的0-1背包问题系列。将分割子集转化为 在nums数组中任取任意元素使其和等于总元素和的一半，即可满足题目条件。

        1、使用一个bool型二维dp数组，dp[i][j] 的含义是：任取nums数组在索引小于等于i之前的元素，能否使其和等于target？ （target为数组元素总和的一半）。

       2、 确定dp数组的含义之后，再进行初始化：首先是第0列的初始化：此时target=0，极端情况，此时可以不选取元素，和即为0，因此将这一列全置为true。  其次是第0行的初始化：此时能选取的元素只有nums[0]，因此将target=nums[0]的地方置为true，其余的都置为false。

        3、最后就是遍历赋值。dp[i][j] 有两个来源：第一个是不选取新的元素，即dp[i][j] = dp[i-1][j] 第二个就是可以选取新的元素，也可以不选取，看哪个是true就选哪个，即dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]] ，dp[i-1][j-nums[i]]即为不选取，此时为什么是i-1呢？因为每个元素只能选取一次，i对应的元素已经被选取了，只能在前i-1个元素中选取了。

        代码如下：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int i=0; i<nums.size(); i++)
        {
            sum += nums[i];
        }
        if(sum % 2 == 1) return false;
        int target = sum / 2; 
        vector<vector<bool>> dp(nums.size(),vector<bool>(target + 1));
        //初始化第一列
        for(int i=0; i<nums.size(); i++)
        {
            dp[i][0] = true;
        }
        //初始化第一行
        for(int i=1; i<=target; i++)
        {
            if(nums[0] == i) dp[0][i] = true;
        }
        for(int i=1; i<nums.size(); i++)
        {
            for(int j=1; j<=target; j++)
            {
                if(j < nums[i]) dp[i][j] = dp[i-1][j]; //此时容量容不下nums[i]这个数，所以不使用nums[i]。
                else dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]; //可以使用nums[i]，也可以不使用。
                //此时为什么是i-1呢？因为每个元素只能选取一次，i对应的元素已经被选取了，只能在前i-1个元素中选取了。
            }
        }
        return dp[nums.size()-1][target];
    }
};

        附上我画的草稿图：

         紫色部分为初始化部分，蓝色部分为遍历赋值部分。