給定一個正整數數組 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

思路：

看到數字的范圍，以及狀態狀態是可以從上一層轉移的，所以考慮動態規劃
當然也可以使用dfs(思路會更簡單一些)

狀態表示：
f[i][j]表示前i個數字，總和為k的方案數量
這里每個數字都是必須選的
狀態轉移：
由于每個數字都相當于是必須選的，所以說不存在不選i的情況，所以不能不選i直接從i-1層狀態轉移過來，不選i這一情況的狀態轉移不用考慮了

狀態轉移方程：

                    if(k-nums[i]+m>=0)f[i][k+m]+=f[i-1][k-nums[i]+m];if(k+nums[i]+m<=2*m)f[i][k+m]+=f[i-1][k+nums[i]+m];

注意初始化的時候應該+=1,因為為第一個數為0的時候直接賦值為1會丟失一種情況

代碼：

class Solution {
public:int f[21][2100];int findTargetSumWays(vector<int>& nums, int target) {int n=nums.size();int m=0;for(int i=0;i<n;i++)m+=nums[i];if(m<abs(target))return 0;memset(f,0,sizeof f);//f[i][k]表示第i個數總和為k的方案數//cout<<f[0][m+nums[0]]<<endl;f[0][m+nums[0]]+=1;//cout<<f[0][m+nums[0]]<<endl;f[0][m-nums[0]]+=1;//這里必須是+=1因為nums[0]可能為0，這時候如果=1就少了一種情況//cout<<f[0][m+nums[0]]<<endl;for(int i=1;i<n;i++)for(int k=-m;k<=m;k++)//枚舉總和{//f[i][k+m]=max(f[i-1][k+m],f[i][k+m]); 由于第i個數不能不選，所以說不能不選i，進而從i-1這個狀態直接轉移過來if(k-nums[i]+m>=0)f[i][k+m]+=f[i-1][k-nums[i]+m];if(k+nums[i]+m<=2*m)f[i][k+m]+=f[i-1][k+nums[i]+m];}return f[n-1][m+target];}
};

運行結果：