思路：石头只能用一次。。。怎么才能让碰撞后重量最小呢，还要转换成动态规划，难以理解。。
看题解：碰撞后重量最小，即将石头分为两组尽可能重量相等。
我理解就是背包容量等于石头总重量的一半，尽可能让背包装满吧，即背包最大容纳重量。

	int lastStoneWeightII(vector<int>& stones) {int sum = 0;for(int i : stones)sum += i;int target = sum / 2;vector<int> dp(target + 1, 0);for(int i = 0; i < stones.size(); i++) {for(int j = target; j >= stones[i]; j--) {dp[j] = max(dp[j], dp[j-stones[i]] + stones[i]);}}return sum - 2 * dp[target];}

哦吼，蒙对了

思路：暴力回溯

	int backtracking(const vector<int>& nums, const int& target, int num, int sum) {if(num == nums.size() - 1 && sum == target) {return 1;}if(num == nums.size() - 1) {return 0;}// cout << nums[num] << " +  " << " " ;int res = backtracking(nums, target, num + 1, sum + nums[num + 1]);// cout << "res : " << res  << endl;// cout << num << " -  " << nums[num] << " ";res += backtracking(nums, target, num + 1, sum - nums[num+1]);// cout << "res : " << res  << endl;return res;}int findTargetSumWays(vector<int>& nums, int target) {return backtracking(nums, target, 0, nums[0]) + backtracking(nums, target, 0, -nums[0]);}

代码有点冗余，，修改一下：

	int backtracking(const vector<int>& nums, const int& target, int num, int sum) {if(num == nums.size() && sum == target) {return 1;}if(num == nums.size()) {return 0;}// cout << nums[num] << " +  " << " " ;int res = backtracking(nums, target, num + 1, sum + nums[num]);// cout << "res : " << res  << endl;// cout << num << " -  " << nums[num] << " ";res += backtracking(nums, target, num + 1, sum - nums[num]);// cout << "res : " << res  << endl;return res;}int findTargetSumWays(vector<int>& nums, int target) {return backtracking(nums, target, 0, 0);}

思路二：动态规划，很抱歉，暂时想不到怎么规划。。。看题解吧
别急，好像有点思路，背包，容量，物品个数。那么是否可以看成，target为背包容量，物品价值可以有+ - nums[i]，最大价值==背包容量的数目？？？瞎猜确实没用，看题解

好好好，再试试
难的是dp的递推公式怎么得出：

1. 填满j（包括j）这么大容积的包，有dp[j]种方法

2. 有哪些来源可以推出dp[j]呢？
   只要搞到nums[i]，凑成dp[j]就有dp[j - nums[i]] 种方法。

   例如：dp[j]，j 为5，

   已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
   已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
   已经有一个3（nums[i]） 的话，有 dp[2]种方法 凑成 容量为5的背包
   已经有一个4（nums[i]） 的话，有 dp[1]种方法 凑成 容量为5的背包
   已经有一个5 （nums[i]）的话，有 dp[0]种方法 凑成 容量为5的背包
   那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。
   dp[j] = dp[j] + dp[j-nums[i]];

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