leetcode [416. 分割等和子集]

(https://leetcode-cn.com/problems/partition-equal-subset-sum/)

看完题之后我们应该可以把问题转化一下：假设nums数组和为sum,如果sum为奇数，就直接false了，否则另target = sum/2。这样问题就转化成了：在nums数组中能否找到某些数，使他们的和为target

最直接的想法就是dfs，暴力去搜，但看了看数据规模，dfs的复杂度是2^n，好像不太行

菜菜的我就止步于此了，看答案发现解法是动态规划，其实就是01背包，背包的最大容量在这一题中变成了target而已，背包九讲中说到01背包中dp[i] [j] 的定义是：前i个物品恰好装进容量为j的背包内所能获得的最大价值。

/*
    在数组中找出一些数，使他们的和等于 target
    除了dfs有没有其他的方法？
*/
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int mx = 0,sum = 0, n = nums.size();
        for (int i = 0; i < n; i++){
            sum += nums[i];
            mx = max(mx, nums[i]);
        }
        if (sum % 2 || mx > (sum/2)) return false;
        if (mx == sum / 2) return true;
        int target = sum / 2;
        vector<vector<int>> dp(n+1, vector<int>(target+1,false));
        dp[0][0] = true;
        for (int i = 1; i <= n; i++){
            //cout<<i<<endl;
            for (int j = 0; j <= target; j++){
                dp[i][j] = dp[i][j] || dp[i-1][j];
                if (j >= nums[i-1])  dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]];
            }
        }
        return dp[n][target];
    }
};

然后就按部就班的写完了，写完之后先是感到空虚（可能因为没有仔细思考），然后自己就在想：我也做过一些动态规划的题目，虽然01背包问题怎么做我给忘了，但翻翻博客也是很快的就捡起来了，但我在看这题的时候根本没有往dp上去想；那么在实际拿到一个题的时候，该如何判断这题可以往dp上想呢？

我觉得1.就是多做题而产生的题感

​ 2.发现好像用dfs去解时间不太允许的时候，就可以考虑用dp（我也不知道对不对（逃）