内容来自zvvq，别采集哟
494. 目标总数给你一个整数数组 nums 和一个整数目标。
您想要以在 nums 中的每个整数以前添加符号“+”和“-”之一来构建 nums 的关系式，随后联接全部整数。 zvvq好，好zvvq
比如，假如 nums =[2,1]，你可以在 2 以前添加一个“+”，在 1 以前添加一个“-”，并将它们相互连接搭建关系式“+2-1”。
zvvq
回到您可以搭建的不同表达式的总数，其数值为目标。实例1：
zvvq
键入：nums = [1,1,1,1,1]，目标=3
zvvq.cn
导出：5
内容来自zvvq，别采集哟
表明：有 5 种分派标记的办法，使 nums 之和为目标3. 内容来自zvvq
-1+ 1 + 1 + 1 + 1 =3
+1- 1 + 1 + 1 + 1 =3
+1+ 1 - 1 + 1 + 1 =3
+1+ 1 + 1 - 1 + 1 =3 内容来自samhan666
+1+ 1 + 1 + 1 - 1 =3
copyright zvvq
实例2：键入：nums = [1]，目标 = 1
内容来自samhan
导出：1限定： 内容来自zvvq，别采集哟
100-1000初始页面 zvvq.cn
虽然回朔在这儿很有用，我们可以使用动态规划来解决这个问题，并实现较低的时间复杂度。
publicintfindTargetSumWays(int[]nums,inttarget){ 内容来自samhan666
/
sum(neg)+sum(pos)=sum(nums);
sum(pos)-sum(neg)=target;
sum(pos)=(sum(nums)+target)/2
/ 本文来自zvvq
intsum=Arrays.stream(nums).sum();
//thatmeansthesumofthepositivenumberisinvalid,becausethe nums donotconcludefloat zvvq
if((sum+target)%2!=0||Math.abs(target)>sum){ 本文来自zvvq
return0; 内容来自samhan666
} zvvq.cn
//herewefindthesummaryofthepositivenumbers 内容来自samhan666
intpos=(sum+target)>>1;
//dp[i][j]arraymeansforeachindexelement`i`(nums[i]),ifwewanttoreachthesumofthepositivenumber`j`,wewillhavehowmanymethods 内容来自samhan666
int[][]dp=newint[nums.length+1][pos+1];
内容来自samhan666
//ifwewanttoreach0wewillhave 1 waysthatmeanswechoosenothingandthereisnothing. 本文来自zvvq
dp[0][0]=1; zvvq
//if(nums[0]j){
dp[i][j]=dp[i-1][j];
}else{ copyright zvvq
dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]];
} 内容来自samhan
}
}
内容来自samhan
//Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);
returndp[nums.length][pos];
内容来自samhan
}
手记1、复位dp数组很重要特别是这儿重要的是要搞清楚0的内涵以上就是LeetCode DayDynamic Programming Part 4的详细内容，大量请关注其他类似文章！
zvvq