力扣学习笔记：416. 分割等和子集_分割等和子集是np问题

题目：https://leetcode-cn.com/problems/partition-equal-subset-sum/
写题过程：一开始想的是先排序，再从中间位置寻找两边是否相等，可是想了想，不行，很容易推翻，最后去看力扣题解学习了一波
算法主体：

1. 这题是经典的NP 完全问题
2. 如果只有一个元素，直接返回fasle
3. 我们可以把问题转换为，寻找数组内是否有数据可以组成所有数据总和的一半。这样我们就可以转换为（0 - 1背包问题）
4. 如果sum总和为奇数，直接返回false
5. 如果数组最大值max_t > sum / 2 的话，直接返回false
6. （①确定状态）创建二位dp数组（n, targrt + 1）(行数是数组的大小，列数我们需要target这个值，所以要加1)，dp[i][j]的值 代表数组[ 0 , i ]之中是否有组合可以达到 j 的值
7. （②边界处理）首先dp数组全为false；dp[i][0] 全是true，一个元素都不取，刚好符合 j == 0 ；而且dp[ 0 ] [ nums[0]] = true ；
8. （③转移方程）如果 j > nums[i] 的话，dp[i][j] = dp[i - 1][j]；反之，dp[i][j] = dp[i - 1][j] | dp[i -1][j - nums[i]]；
9. 时间复杂度：O(N * target)；两成循环占大头
   10.空间复杂度：O（N * targrt）)

源代码：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();

        if(n < 2){
            return false;
        }

        int total = 0;
        int max_t = INT_MIN;
        for(int t : nums){
            total += t;
            max_t = max(max_t, t); 
        }

        if(total % 2 == 1){
            return false;
        }

        int target = total / 2;
        if(target < max_t){
            return false;
        }

        vector<vector<bool>> dp(n,vector<bool>(target + 1,false));

        for(int i = 0; i < n; ++i){
            dp[i][0] = true;
        }

        dp[0][nums[0]] = true;

        for(int i = 1; i < n; ++i){
            for(int j = 1; j < target + 1; ++j){ 
                if(j >= nums[i]){
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i]];
                }
                else{
                    dp[i][j] = dp[i - 1][j];
                } 
            }
        }

        return dp[n - 1][target];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47