给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

先转化为求正数部分恰好等于目标值的方案总数问题, 即恰好装满背包的方案数.

定义边界条件:

$$ d p [ 0 ] [ j ] = \left\{ \begin{array} { l l } 1 , & j = 0 \\ 0 , & j \geq 1 \end{array} \right. $$

当没有元素时, 只有总重量为0的解法, 因此只有 dp[0][0]=1

$\begin{array} { l } \text { 如果 } j < n u m , \text { 则不能选 } n u m , \text { 此时有 } d p [ i ] [ j ] = d p [ i - 1 ] [ j ] ; \\ \text { 如果 } j \geq n u m , \text { 则如果不选 } n u m , \quad \text { 方案数是 } d p [ i - 1 ] [ j ] , \text { 如果选 } n u m , \text { 方案数是 } d p [ i - 1 ] [ j - n u m ] , \\ \text { 此时有 } d p [ i ] [ j ] = d p [ i - 1 ] [ j ] + d p [ i - 1 ] [ j - n u m ] _ { 0 } \end{array}$

所以状态转移方程为

$$ d p [ i ] [ j ] = \left\{ \begin{array} { l l } d p [ i - 1 ] [ j ] , & j < \text { nums } [ i ] \\ d p [ i - 1 ] [ j ] + d p [ i - 1 ] [ j - \text { nums } [ i ] ] , & j \geq \text { nums } [ i ] \end{array} \right. $$

题解:

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        for (int &a:nums) sum+=a;
        if ((sum+target)%2) return 0;
        int p_sum = (sum+target)/2;
        if (p_sum<0) return 0;

        vector<vector<int>> dp(nums.size()+1, vector<int>(p_sum+1, 0));
        // 总重为0, 则方案数为1
        dp[0][0] = 1;

        for (int i=1; i<=nums.size(); i++){
            for (int j=p_sum; j>=0; j--){
                if (j>=nums[i-1])
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
                else
                    dp[i][j] = dp[i-1][j];
            }
        }
        return dp.at(nums.size()).at(p_sum);
    }
};