2023.8.14

????????一杯茶，一包煙，一道dp做一天...

? ? ? ? ps：nums[i]均大于等于0。本題先轉化為0-1背包問題：將數組元素分成兩堆：一堆為正號，另一堆為負號。設正號堆的和為x，則負號堆的和為sum-x。（sum為數組元素總和）。? ? ? ? ? ? ? ?于是：x-(sum-x) =target ,可以推出 x = (target+sum)/2 。x必須為偶數，為奇數直接返回0。

? ? ? ? 于是此時背包的大小相當于x，物品為數組nums。 dp[i]的含義為：裝滿大小為 i 的背包的 方法種數。? 具體代碼如下：

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for(int i=0; i<nums.size(); i++){sum += nums[i];}if((sum + target) % 2 == 1) return 0;int capacity = (sum + target)/2;if(capacity < 0) return 0;vector<int> dp(capacity + 1);dp[0] = 1;for(int i=0; i<nums.size(); i++){for(int j=capacity; j>=nums[i]; j--){//第一項是不使用nums[i]時裝滿背包的方法種數，第二項是使用nums[i]時裝滿背包的方法種數。dp[j] = dp[j] + dp[j - nums[i]];}}return dp[capacity];}
};