您现在的位置是:首页 >其他 >494. 目标和网站首页其他

494. 目标和

m0_54386352 2024-06-08 00:00:02
简介494. 目标和

目录

1、题目描述

2、思路:动态规划

2.1、确定dp数组及x下标含义

2.2、确定递推公式

2.3、dp数组初始化

2.4、确定遍历顺序

3、C++实现如下


1、题目描述

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ,然后串联起所有整数,可以构造一个 表达式 :

例如,nums = [2, 1] ,可以在 2 之前添加 '+' ,在 1 之前添加 '-' ,然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1:

输入:nums = [1,1,1,1,1], target = 3
输出:5
解释:一共有 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], target = 1
输出:1
 

提示:

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/target-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2、思路:动态规划

仔细阅读题目可以发现,可以理解为将整个数组分为两个子集,其中一个子集减去另一个子集有多少种实现方法。

假设在数字前放加号的数字总和为x,那么放减号的数字总和为sum-x,而目标target = x-(sum-x),即x = (target+sum)/2,那么就将问题转换为了动态规划。

如果 target+sum 不能整除2,那么没有方法可以实现题目要求。因为nums[i] >= 0,所以sum为非负数,所以,如果背包容量left求出小于0的数,则没有方案。

因为每个物品只能使用一次,所以,该题为01背包问题。

2.1、确定dp数组及x下标含义

dp[j] 表示:填满j(包括j)这么大容积的包,有dp[j]种方法

2.2、确定递推公式

有了nums[i],凑成dp[j]就有dp[j - nums[i]] 种方法。

例如:dp[j],j 为5,

如果已经有一个1(nums[i]) ,有 dp[4]种方法 凑成 容量为5的背包。

如果已经有一个2(nums[i]) ,有 dp[3]种方法 凑成 容量为5的背包。

如果已经有一个3(nums[i]) ,有 dp[2]中方法 凑成 容量为5的背包

如果已经有一个4(nums[i]) ,有 dp[1]中方法 凑成 容量为5的背包

如果已经有一个5 (nums[i]),有 dp[0]中方法 凑成 容量为5的背包

那么凑整dp[5]就是把所有的 dp[j - nums[i]] 累加起来。

所以求组合类问题的公式,都使用类似的方法处理:

dp[j] += dp[j - nums[i]]

2.3、dp数组初始化

当背包容量为0时,有1种方法来放物品,就是什么都不放,遇到物品再说。

所以,dp[0] 初始化为0,而其他的dp数组需要通过其他的dp数组累加计算而来,所以初始化为0.

2.4、确定遍历顺序

外层从前往后,内层从大到小。

3、C++实现如下

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int length = nums.size();
        int sum = 0;
        for(int i = 0;i<length;++i){
            sum+=nums[i];
        }
        int left = target + sum;
        if(left%2!=0||left<0){
            return 0;
        }
        left/=2;
        
        vector<int> dp(left+1);
        dp[0] = 1;
        for(int i = 0;i<length;++i){
            for(int j = left;j>=nums[i];--j){
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[left];
    }
};

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。