题目

前沿

这个题目，我开始的想法是深度搜索的题目，也就是去遍历所有解，然后返回统计结果。但是这种方法复杂度太高，如果没有优化到位，根本没有办法AC这道题。但是LedeCode给出了一个DP的解法，这个解法巧妙就在于转化了针对当前值的状态改变的一个问题，转成了针对当前序列的一个选取的问题。 如果不考虑状态的话，那么就是一个可以采用统计的两个状态选取还是不选取。这样DP的结果就是统计的数目，否则对于+还是-则选则一个好的状态转移方程。 代码

class Solution {
          
   
public:
    int findTargetSumWays(vector<int>& nums, int target) {
          
   
        int sum = 0;
        for (int& num : nums) {
          
   
            sum += num;
        }
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {
          
   
            return 0;
        }
        int n = nums.size(), neg = diff / 2;
        vector<vector<int>> dp(n + 1, vector<int>(neg + 1));
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
          
   
            int num = nums[i - 1];
            for (int j = 0; j <= neg; j++) {
          
   
                dp[i][j] = dp[i - 1][j];
                if (j >= num) {
          
   
                    dp[i][j] += dp[i - 1][j - num];
                }
            }
        }
        return dp[n][neg];
    }
};
链接：https://leetcode-cn.com/problems/target-sum/solution/mu-biao-he-by-leetcode-solution-o0cp/

这个是非优化的版本。