LeetCode算法笔记--目标和

算法题热题HOT100 背包问题

字数统计: 322阅读时长: 1 min

 2021/02/23   Share

LeetCode算法笔记-Day70

494. Target Sum

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:

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.

0-1背包问题

P是正子集，N是负子集

sum(P) - sum(N) = target
（两边同时加上sum(P)+sum(N)）

sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
(因为 sum(P) + sum(N) = sum(nums))

2 * sum(P) = target + sum(nums)

sum(P) = ( target + sum(nums) ) / 2

题目转化为01背包，也就是能组合成容量为sum(P)的方式有多少种,一种组合中每个数字只能取一次。
解决01背包问题使用的是动态规划的思想。

Answer：

/**
 * @param {number[]} nums
 * @param {number} S
 * @return {number}
 */
var findTargetSumWays = function(nums, S) {
    let sums = 0;
    nums.map( e=>sums += e )

    if (sums < S || (S + sums) % 2 == 1) return 0;

    let p = (S + sums) >> 1,
        dp = new Array(p + 1).fill(0);
    dp[0] = 1;
    nums.map(num => {
        for (let i = p; i >= num; i--) {
            dp[i] += dp[i - num];
        }
    })
    return dp[p];
};

Next Post

LeetCode算法笔记--每日温度
Previous Post

LeetCode算法笔记--除自身以外数组的乘积

CATALOG

1. LeetCode算法笔记-Day70
1. 1.1. 494. Target Sum
2. 1.2. 0-1背包问题
  1. 1.2.1. Answer：

