• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Leetcode 494 目标和发展计划


Recommended Posts

地址https://leetcode-cn.com/problems/target-sum/

给你一个整数数组nums和一个整数目标。

在数组中的每个整数前添加“”或“-”,然后连接所有整数以构造一个表达式:

比如nums=[2,1],可以在2前加'',在1前加'-',然后串联起来得到表达式' 2-1 '。

返回上述方法可以构造的不同表达式的个数,运算结果等于target。

示例1:

输入:nums=[1,1,1,1,1],目标=3

输出:5

说明:有五种方法可以使最终目标和为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

提示:

1=nums.length=20

0=nums=1000

0=sum(nums)=1000

-1000=目标=1000

解释

1暴力遍历每个元素可以有正反选择2 20

DP不能作为指标,因为是负数。所有计算额外增加1000。

DP通过公式推导,变成01背包。

2方案代码

类别解决方案{

公共:

int findTargetSumWays(vector int nums,int target) {

int DP[22][2010];memset(dp,0,sizeof DP);

DP[0][1000]=1;目标=1000;

for(int I=1;I=nums . size();i ) {

int val=nums[I-1];

for(int j=2000;j=0;j - ) {

if (j - val=0) {

DP[j]=DP[I-1][j-val];

}

if (j val=2000) {

DP[j]=DP[I-1][j val];

}

}

}

return DP[nums . size()][target];

}

};

我的视频问题解决空间

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now