力扣-动态规划-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];}
};