leecode494.目标和

 这道题目第一眼感觉就不像是动态规划，可以看出来是回溯问题，但是暴力回溯超时，想要用动态规划得进行一点数学转换

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int n=nums.size(),bagWeight=0,sum=0;for(int i=0;i<n;i++)sum+=nums[i];//target绝对值大于sum时方法为0if(abs(target)>sum)return 0;//(sum+target)/2有余数时方法为0if((sum+target)%2)return 0;bagWeight=(sum+target)/2;vector<int> dp(bagWeight+1,0);dp[0]=1;for(int i=0;i<n;i++)for(int j=bagWeight;j>=nums[i];j--)dp[j]+=dp[j-nums[i]];return dp[bagWeight];}
};