​2021-05-07：给定一个数组arr，你可以在每个数字之前决定+或者-

2021-05-07：给定一个数组arr，你可以在每个数字之前决定+或者-，但是必须所有数字都参与 ，再给定一个数target，请问最后算出target的方法数是多少？

福大大 答案2021-05-07：

优化点一 :

你可以认为arr中都是非负数

因为即便是arr中有负数，比如3,-4,2

因为你能在每个数前面用+或者-号

所以3,-4,2其实和3,4,2达成一样的效果

那么我们就全把arr变成非负数，不会影响结果的

优化点二 :

如果arr都是非负数，并且所有数的累加和是sum

那么如果target<sum，很明显没有任何方法可以达到target，可以直接返回0

优化点三 :

因为题目要求一定要使用所有数字去拼target，

所以不管这些数字怎么用+和-折腾，最终的结果都一定不会改变奇偶性

所以，如果所有数的累加和是sum，

并且与target的奇偶性不一样，没有任何方法可以达到target，可以直接返回0

优化点四 :

比如说给定一个数组, arr = 1, 2, 3, 4, 5 并且 target = 3

其中一个方案是 : +1 -2 +3 -4 +5 = 3

该方案中取了正的集合为P = {1，3，5}

该方案中取了负的集合为N = {2，4}

所以任何一种方案，都一定有 sum(P) - sum(N) = target

现在我们来处理一下这个等式，把左右两边都加上sum(P) + sum(N)，那么就会变成如下：

sum(P) - sum(N) + sum(P) + sum(N) = target + sum(P) + sum(N)

2 * sum(P) = target + 数组所有数的累加和

sum(P) = (target + 数组所有数的累加和) / 2

也就是说，任何一个集合，只要累加和是(target + 数组所有数的累加和) / 2

那么就一定对应一种target的方式

也就是说，比如非负数组arr，target = 7, 而所有数累加和是11

求使用所有数字的情况下，多少方法最后形成7？

其实就是求有多少个子集的累加和是9 -> (7 + 11) / 2

优化点五 :

二维动态规划的空间压缩技巧

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    arr := []int{1, 1, 1, 1, 1}
    target := 3
    ret := findTargetSumWays3(arr, target)
    fmt.Println(ret)
}

func findTargetSumWays3(arr []int, target int) int {
    sum := 0
    for _, n := range arr {
        sum += n
    }
    return twoSelectOne(sum < target || ((target&1)^(sum&1)) != 0, 0, subset(arr, (target+sum)>>1))
}

func subset(nums []int, s int) int {
    dp := make([]int, s+1)
    dp[0] = 1
    for _, n := range nums {
        for i := s; i >= n; i-- {
            dp[i] += dp[i-n]
        }
    }
    return dp[s]
}

func twoSelectOne(condition bool, a int, b int) int {
    if condition {
        return a
    } else {
        return b
    }
}

执行结果如下：

图片

左神java代码