給你一個整數數組 nums 和一個整數 target 。
向數組中的每個整數前添加 ‘+’ 或 ‘-’ ，然后串聯起所有整數，可以構造一個 表達式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串聯起來得到表達式 “+2-1” 。
返回可以通過上述方法構造的、運算結果等于 target 的不同 表達式 的數目。

示例 1：
輸入：nums = [1,1,1,1,1], target = 3
輸出：5
解釋：一共有 5 種方法讓最終目標和為 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：
輸入：nums = [1], target = 1
輸出：1

提示：
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

這道題想要用01背包解決需要非常了解01背包，看到這道題到底該怎么往01背包上去靠呢？下面來分析一下：
先看題，找找哪里有01背包的特點和我們能得到的信息
首先，我們可以發現每一種方法里面nums[i]都只能使用一次
其次，nums[i]類似于01背包中的物品重量和物品價值；
現在只差一個條件就是背包容量bagsize了，bagsize該怎么求呢？
我們單看每種方法可以發現，如果設加法的總和為a， nums數組和為sum
那么減法的總和就為sum - a，
所以target = a - （sum - a），即加法和減去減法和
上式變換一下就可以得到 a = (target + sum) / 2；
這時問題就可以化為：裝滿容量為a背包，有幾種方法
即a就是bagsize
當然這里還需要注意一個點，就是a取整的問題

if ((target + sum) % 2) return 0;

接下來就來看看這個背包問題轉化后的樣子：
背包容量：bagsize = (target + sum) / 2；
第i個物品質量：nums[i];
第i個物品價值：nums[i];

接下來就開始遞歸分析了：
1，dp[j] 表示 j 容量下，填滿后的方法數；
2，想要求dp[j]需要求出dp[j - nums[i]]相加就可以了，即

dp[j] += dp[j - nums[i]];

3，初始值需要注意，dp[0] = 1，即裝滿容量為0的背包，有1種方法，就是裝0件物品。
如果忘記初始化那么所有情況下的方法數都會為0；
4，遍歷順序和之前一樣，外層循環物品，內層逆序循環背包容量；

代碼如下：

class Solution { public:int findTargetSumWays(vector<int>& nums, int target) {int n = nums.size(), sum = 0;for (int i = 0; i < n; ++i) sum += nums[i];if (target > sum) return 0;if ((target + sum) % 2) return 0;int bagsize = (target + sum) / 2;vector<int> dp(bagsize + 1, 0);dp[0] = 1;for (int i = 0; i < n; ++i) {for (int j = bagsize; j >= nums[i]; --j) dp[j] += dp[j - nums[i]];}return dp[bagsize];} };

總結

這道題值得注意的就是初始問題向01背包的轉化過程，并且還需要注意轉移方程和之前有不同，其實這個轉移方程多用于求這種組合類（計數）的問題，之前那個轉移方程求得都是最值問題，所以可以有個印象，方便快速判斷轉移方程；

總結

以上是生活随笔為你收集整理的目标和（01背包应用）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。