首页 > 其他分享 >494.Target Sum

494.Target Sum

时间:2023-03-16 19:22:59浏览次数:37  
标签:target nums int Sum symbols 494 sum dp Target

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5 Explanation: -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 There are 5 ways to assign symbols to make the sum of nums be target 3.

 

sum(P)-sum(n)=target; sum(P)-sum(n)+sum(P)+sum(n)=target+sum(P)+sum(n); 2*sum(P)=target+sum(nums); sum(P)=(target+sum(nums))/2;   最后转换为求sum(P),即数组中有几个组合加起来等于sum(P) dp[i]的意思是:元素和为i的话有几种情况, 当前元素为4时,则dp[i] = dp[i] + dp[i-4]; dp[9] = dp[9] + dp[9-4]; dp[8] = dp[8] + dp[8-4]; dp[7] = dp[7] + dp[7-4]; dp[6] = dp[6] + dp[6-4]; dp[5] = dp[5] + dp[5-4]; dp[4] = dp[4] + dp[4-4];  
public static int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
if (target > sum || (sum + target) % 2 == 1)
return 0;
return subsetSum(nums, (sum + target) / 2);
}

private static int subsetSum(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1; //C(0,0)=1
for (int i = 0; i < nums.length; i++) {
for (int j = target; j >= 0; j--) {
if (j >= nums[i])
dp[j] += dp[j - nums[i]];
}
}
return dp[target];
}

标签:target,nums,int,Sum,symbols,494,sum,dp,Target
From: https://www.cnblogs.com/MarkLeeBYR/p/17223865.html

相关文章

  • 416.Partition Equal Subset Sum
    Givena non-empty arraycontaining onlypositiveintegers,findifthearraycanbepartitionedintotwosubsetssuchthatthesumofelementsinbothsubse......
  • 算法随想Day38【动态规划】| LC494-目标和、LC1049-最后一块石头的重量Ⅱ、LC474-一和
    01背包的应用分割等和子集:给一个weight的背包,尽量往里塞满,如果有刚刚塞满的组合,则返回true。问的是是否存在刚刚好塞满weight背包的组合。最后一块石头的重量Ⅱ:给一个......
  • Android compileSdkVersion、buildToolsVersion、minSdkVersion、targetSdkVersion
    1、CompileSdkVersion是你SDK的版本号,也就是APILevel,指定了Gradle编译你的App时使用的AndroidAPI版本  2、buildeToolVersion是你构建工具的版本,其中包括了打包工具......
  • Amazon Cloud Technology China Summit
    2022.10.13在本次为期2天的峰会上,亚马逊云科技发布了云计算技术趋势展望,宣布“连中外、襄百业、携伙伴、促绿色”四大战略举措,进一步利用亚马逊云科技全球优势和资源,更好......
  • Baidu Cloud Intelligence Summit
    2022.12.27智能计算的发展为人工智能推动实体经济数智化升级提供算力支撑,AI安全的兼程并进更是支撑我国科技自立自强、实现高质量发展的必经之路,百度智能云与中国电子技术......
  • A. K-divisible Sum
    A.K-divisibleSum思路\[ans=\left\lceil\frac{kx}{n}\right\rceil\]\[x=x_{min}\ge\left\lceil\frac{n}{k}\right\rceil\]代码点击查看代码#inc......
  • Square(n) Sum
    InstructionsCompletethesquaresumfunctionsothatitsquareseachnumberpassedintoitandthensumstheresultstogether.Forexample,for[1,2,2]itsh......
  • ARC158C All Pair Digit Sums 题解
    题目链接题意设\(f(x)\)表示\(x\)的各位之和。例如\(f(158)=1+5+8=14,f(2023)=2+0+2+3=7,f(1)=1\)等。给定一个正整数序列\(A=(A_1,...,A_N)\),求\(\sum_{i=1}^N......
  • CF1785D Range = √Sum 题解
    题目传送门(第一次CF场切绿欸)题意考虑将这段序列的平均数设为\(4n\),那么总和就会是\(4n^2\),这时候就需要让最值差等于\(2n\),直接让他等于\(3n\)和\(5n\)就可......
  • Delegate的Target,Method
    在C#中,Delegate是一种引用方法的类型,可以将方法视为对象进行传递和操作。Delegate类型的实例可以用来引用一个或多个方法,然后可以将这些引用作为参数传递给其他方法,或......