|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
题目描述:
- 给定一个非负整数数组,a1, a2, ..., an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。
- 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
-  
- 示例:
- 输入:nums: [1, 1, 1, 1, 1], S: 3
- 输出:5
- 解释:
- -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
- 一共有5种方法让最终目标和为3。
-  
- 提示:
- 数组非空,且长度不会超过 20 。
- 初始的数组的和不会超过 1000 。
- 保证返回的最终结果能被 32 位整数存下。
- 来源:力扣(LeetCode)
- 链接:https://leetcode-cn.com/problems/target-sum
- 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码
- class Solution {
- public:
- int findTargetSumWays(vector<int>& nums, int S) {
- int sum = 0;
- for(auto cha : nums)sum += cha;
- if(abs(S) > sum)return 0;
- int t = sum * 2 + 1, len = nums.size();
- vector<vector<int> > dp(len, vector<int>(t, 0));
- //初始化
- if(nums[0] == 0){
- dp[0][sum] = 2;
- }else{
- dp[0][sum + nums[0]] = 1;
- dp[0][sum - nums[0]] = 1;
- }
- for(int i = 1; i < len; i++){
- for(int j = 0; j < t; j++){
- int l = (j - nums[i]) >= 0 ? j - nums[i] : 0;
- int r = (j + nums[i]) < t ? j + nums[i] : 0;//t这里是位置
- dp[i][j] = dp[i - 1][l] + dp[i - 1][r];
- }
- }
- return dp[len - 1][sum + S];
- }
- };
复制代码
参考链接:https://leetcode-cn.com/problems ... uo-cheng-by-keepal/ |
|