# 494.目标和

## 问题描述
[494.目标和](https://leetcode.cn/problems/target-sum/)

## 解题思路
本题表面上说添加'+'或者'-'，实际上就是在这个数组中选择一些数，使这些数的总和为$\max((sum + target) / 2, (sum - target) / 2)$。从而转换成[01背包问题](https://www.zwyyy456.vercel.app/zh/posts/tech/01-pack-problem/)，利用动态规划求解，当然也可以利用回溯法求解。

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

## 代码
```cpp
#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];
    }
};
```