力扣-动态规划-494 目标和

思路

1. dp数组定义：任意装 0 - i 下标的元素，装满容量 j 共有dp [i ,  j ] 种装法
2. 递推公式：

   for (int i = 1; i < m; i++) {
       for (int j = 0; j <= cap; j++) {
           if (nums[i] > j) {
               dp[i][j] = dp[i - 1][j];
           } else {
               dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
           }
       }
   }

   分为两种情况的总和：放第i个物品装满j，和不放第i个物品装满j - nums[i]

3. dp数组初始化：第一行有恰好放进去，置为1，dp[0][0] 为0，第一列考虑0的个数
4. 遍历顺序：左向右，上向下
5. 时间复杂度：     

代码

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int n : nums)
            sum += n;
        if (( sum + target) % 2 == 1)
            return 0;
        int cap = (sum + target) / 2;
        if(cap < 0) return 0;
        int m = nums.size();
        vector< vector<int> > dp(m, vector<int>(cap + 1, 0));

        if (nums[0] <= cap)
            dp[0][nums[0]] = 1;
        dp[0][0] = 1;

        int numZero = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0)
                numZero++;
            dp[i][0] = (int) pow(2.0, numZero);
        }

        for (int i = 1; i < m; i++) {
            for (int j = 0; j <= cap; j++) {
                if (nums[i] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
                }
            }
        }

        return dp[m-1][cap];
    }
};