类似01背包

该问题中，j-v<0时候，这个状态也是合法的，也需要记录，所以数组的第二维需要用偏移量，防止数组越界。

$ 时间复杂度O(NM)，空间复杂度(N2M)$

参考文献

lc究极班

AC代码

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int m) {
        //特判无解
        if (m < -1000 || m > 1000) return 0;
        int n = nums.size(), d = 1500;//偏移量
        vector<vector<int>> f(n + 1, vector<int>(1500 * 2 + 10, 0));
        //DP
        f[0][d] = 1;
        for (int i = 1 ; i <= n ; i ++){
            int v = nums[i - 1];
            for (int j = -1000 ; j <= 1000 ; j ++){
                if (j - v >= -1000) 
                    f[i][j + d] += f[i - 1][j - v + d];
                if (j + v <= 1000)
                    f[i][j + d] += f[i - 1][j + v + d];
            }
        }
        return f[n][m + d];
    }
};