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