问题描述 链接到标题

494.目标和

解题思路 链接到标题

本题表面上说添加’+‘或者’-’，实际上就是在这个数组中选择一些数，使这些数的总和为$\max((sum + target) / 2, (sum - target) / 2)$。从而转换成01背包问题，利用动态规划求解，当然也可以利用回溯法求解。

在本题中，dp[i][j]应该表示为考虑前i个数时，使选择的数总和为j的方法数。

代码 链接到标题 

#include <vector>
using std::vector;
class Solution {
  private:
    int max(int a, int b) {
        return a > b ? a : b;
    }

  public:
    int findTargetSumWays(vector<int> &nums, int target) {
        int sum = 0;
        vector<int> my_num(nums.size() + 1, 0);
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            my_num[i + 1] = nums[i];
        }
        if ((sum + target) % 2 == 1)
            return 0;
        vector<int> res(1001, 0);
        res[0] = 1;
        target = max((sum + target) / 2, (sum - target) / 2);
        // int cnt = 0;
        for (int i = 1; i <= nums.size(); i++) {
            for (int j = target; j >= my_num[i]; j--) {
                // if (my_num[i] == 0)
                //     res[j] = res[j] + 1;
                // else
                //     res[j] = max(res[j], res[j - my_num[i]]);
                res[j] = res[j] + res[j - my_num[i]];
            }
        }
        return res[target];
    }
};