This is the 22nd day of my participation in the More text Challenge. For details, see more text Challenge

Objective and (Question No. 494)

The title

You are given an integer array nums and an integer target.

We can construct an expression by adding a ‘+’ or ‘-‘ to each integer in an array, and then concatenating all the integers:

  • For example,nums = [2, 1], can be in2Before you add'+'In the1Before you addThe '-'And then we can string them together to get the expression"+ 2-1" 。

Returns the number of different expressions that can be constructed using the above method, where the result of the operation is equal to target.

Example 1:

Input: nums = [1.1.1.1.1], target = 3Output:5Explanation: There are altogether5One way to make the end goal sum3. -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
Copy the code

Example 2:

Input: nums = [1], target = 1Output:1
Copy the code

Tip:

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

link

Leetcode-cn.com/problems/ta…

explain

This one, this one is classical dynamic programming.

Let’s look at the brute force solution first, and the brute force solution is very simple, you just recurse and find all the possibilities, there’s nothing to be said about it.

The key is the idea of dynamic programming, the author is thinking on the way home, thinking all the way there is no good idea, even if this problem is the difference of the dynamic programming four words on the topic.

It seems that the answer to know the original problem is through some calculations to dynamic programming, the author’s DP has been stuck in the symbol above, with the symbol is not very convenient DP, because the formula has been unable to come out.

So how do you get rid of the sign? So this is going to require some calculation.

The official explanation is directly quoted here, and the author will not translate it twice 👇 :

If the sum of the elements in the notation group is sum, and the sum of the elements added with a – sign is neg, then the sum of the remaining elements added with a + is sum−neg, and the result of the expression is


( s u m – n e g ) – n e g = s u m – 2 ⋅ n e g = t a r g e t (the sum – neg) – neg = sum – 2 ⋅ neg = target

namely


n e g = s u m – t a r g e t 2 Neg = \ frac {sum – target} {2}

Since all elements in nums are non-negative integers, neg must also be non-negative integers, so sum−target is a non-negative even number. Return 0 if this condition is not met.

If the above equation is true, the problem is transformed to select several elements in the array NUMS, make the sum of these elements equal to NEg, and calculate the number of schemes of selected elements. We can do dynamic programming.

Then the process is very simple, using dynamic programming to find dp[I][j], when j is neg, is the answer we want.

Your own answer

There is no

A Better way (violence)

Violent law is simple, 👇 :

var findTargetSumWays = function(nums, target) {
  var count = 0
  function DFS(sum, index) {
    if (index === nums.length) {
      if (sum === target) {
        count++
      }
    } else {
      DFS(sum + nums[index], index + 1)
      DFS(sum - nums[index], index + 1)
    }
  }
  DFS(0.0)
  return count
};
Copy the code

Let’s just do a depth-first search function, and then call it recursively, and we’re done, there’s no extra trick, and every time we get to the end, we’re going to tell if sum is equal to target, it’s easy.

A better approach (dynamic Programming)

DP is a little bit complicated here. Before starting DP, there are two steps to prepare. First, get all the numbers and then find Neg and Diff for pruning.

Then, the DP operation is performed according to neg, and the possibility that the sum of all the numbers is neg is the answer to this question.

var findTargetSumWays = function(nums, target) {
  var sum = 0
      diff = 0
      neg = 0
      len = nums.length
      dp = null
  for (const num of nums) {
     sum += num
  }
  diff = sum - target
  / / the pruning
  if (diff < 0 || diff % 2! = =0) return 0
  neg = diff / 2
  dp = Array.from({length: len + 1}, () = > new Array(neg + 1).fill(0))
  dp[0] [0] = 1
  for (let i = 1; i <= len; i++) {
    var num = nums[i - 1]
    for (let j = 0; j <= neg; j++) {
      dp[i][j] = dp[i - 1][j]
      if (j >= num) {
        dp[i][j] += dp[i - 1][j - num]
      }      
    }    
  }
  return dp[len][neg]
};
Copy the code

The pruning process is this line of code 👇 :

if (diff < 0 || diff % 2! = =0) return 0
Copy the code

In the first case, since all the numbers are non-negative integers, if diff is less than 0, then target is greater than the sum of all the numbers, in which case there is obviously no possibility.

In the second case, since we have the equation neg = diff / 2 in the explanation, if diff is not divisible by two, that means that neg is a decimal, and since all the numbers are integers, it is obviously impossible to form a decimal, so there is no possibility in this case.

After the completion of the pruning is the classical DP, here not to repeat, if you do not understand more than a few times, this degree of DP is not difficult to understand.

Better approach (Dynamic programming -> Dimension reduction)

Another classic dynamic programming dimension reduction operation, because each new DP result is only related to the last result, obviously only need to save the last result.

Note, however, that all inner loops need to be operated in reverse order 👇 because the value in dp[i-1][] needs to be guaranteed:

var findTargetSumWays = function(nums, target) {
    let sum = 0;
    for (const num of nums) {
        sum += num;
    }
    const diff = sum - target;
    if (diff < 0 || diff % 2! = =0) {
        return 0;
    }
    const neg = diff / 2;
    const dp = new Array(neg + 1).fill(0);
    dp[0] = 1;
    for (const num of nums) {
        for (letj = neg; j >= num; j--) { dp[j] += dp[j - num]; }}return dp[neg];
};
Copy the code




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ