[leetcode]494. 目标和(01 背包dp)

题目链接
题意

给定n个数的非负数组，每个数都要选，可以选这个数的相反数或者自己，求有多少种方案使得和为target
思路

令s为数组的和，p为数组中选正数的和，p为数组中选负数的和的绝对值，则有                                                   {                                                                                                     p                                              +                                              q                                              =                                              =                                              s                                                                                                                                                  p                                              −                                              q                                              =                                              =                                              ∣                                              t                                              a                                              r                                              g                                              e                                              t                                              ∣                                                                                                       ⇒                                       {                                                                                                     p                                              =                                              s                                              +                                              ∣                                              t                                              a                                              r                                              g                                              e                                              t                                              ∣                                              >                                              >                                              1                                                                                                                                                  q                                              =                                              s                                              −                                              ∣                                              t                                              a                                              r                                              g                                              e                                              t                                              ∣                                              >                                              >                                              1                                                                                                             \begin{cases} p+q==s\\ p-q==|target| \end{cases} \Rightarrow \begin{cases} p=s+|target|>>1\\ q=s-|target|>>1 \end{cases}                     {p+q==sp−q==∣target∣​⇒{p=s+∣target∣>>1q=s−∣target∣>>1​
以是题目转化为了
从n个元素中找出一些数 和为p or q的方案数
就酿成01 背包了
Code

1. class Solution {
2. public:
3.     int findTargetSumWays(vector<int>& nums, int target) {
4.         int n = nums.size(),s=accumulate(nums.begin(),nums.end(),0)-abs(target);
5.         int m=s>>1;
6.         if( s<0 || s%2 ) return 0;
8.         vector<int>a(n+1);
9.         for(int i=0;i<n;i++) a[i+1]=nums[i];
11.         vector dp(n+1,vector<int>(m+1));
12.         dp[0][0]=1;
14.         for(int i=1;i<=n;i++){
15.             for(int j=0;j<=m;j++){
16.                 if(j<a[i]) {
17.                     dp[i][j]=dp[i-1][j];
18.                 }else{
19.                     dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]];
20.                 }
21.             }
22.         }
23.         return dp[n][m];
24.         
25.     }
26. };

复制代码

空间优化

1. class Solution {
2. public:
3.     int findTargetSumWays(vector<int>& nums, int target) {
4.         int n = nums.size(),s=accumulate(nums.begin(),nums.end(),0)+abs(target);
5.         if( s<0 || s%2 ) return 0;
6.         int m=s>>1;
8.         vector<int>a(n+1);
9.         for(int i=0;i<n;i++) a[i+1]=nums[i];
11.         vector<int> dp (m+1);
12.         dp[0]=1;
14.         for(int i=1;i<=n;i++){
15.             for(int j=m;j>=a[i];j--){
16.                 dp[j]+=dp[j-a[i]];
17.             }
18.         }
19.         return dp[m];
20.         
21.     }
22. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。