2021-02-25：给定一个负数数组arr，请把arr中所有的数分成两个汇合。如果arr长度为偶数，两个汇合蕴含数的个数要一样多；如果arr长度为奇数，两个汇合蕴含数的个数必须只差一个。请尽量让两个汇合的累加和靠近，返回最靠近的状况下，较小汇合的累加和。
福哥答案2020-02-25：
天然智慧即可。
1.递归。有代码。
2.动静布局。dp是三维数组。有代码。
代码用golang编写，代码如下：
package mainimport "fmt"const INT_MAX = int(^uint(0) >> 1)const INT_MIN = ^INT_MAXfunc main() { arr := []int{1, 2, 3, 4, 100} ret := right1(arr) fmt.Println("1.递归：", ret) ret = right2(arr) fmt.Println("2.动静布局：", ret)}func right1(arr []int) int { if len(arr) < 2 { return 0 } sum := 0 for _, v := range arr { sum += v } if len(arr)&1 == 0 { return process1(arr, 0, len(arr)/2, sum/2) } else { ret1 := process1(arr, 0, len(arr)/2, sum/2) ret2 := process1(arr, 0, len(arr)/2+1, sum/2) if ret1 < ret2 { return ret2 } else { return ret1 } }}func process1(arr []int, i int, picks int, rest int) int { if i == len(arr) { if picks == 0 { return 0 } else { return -1 } } else { p1 := process1(arr, i+1, picks, rest) p2 := -1 next := -1 if arr[i] <= rest { next = process1(arr, i+1, picks-1, rest-arr[i]) } if next != -1 { p2 = arr[i] + next } return GetMax(p1, p2) }}func right2(arr []int) int { if len(arr) < 2 { return 0 } sum := 0 for _, v := range arr { sum += v } sum >>= 1 N := len(arr) M := (len(arr) + 1) >> 1 dp := make([][][]int, N) for i := 0; i < N; i++ { dp[i] = make([][]int, M+1) for j := 0; j < M+1; j++ { dp[i][j] = make([]int, sum+1) for k := 0; k < sum+1; k++ { dp[i][j][k] = INT_MIN } } } for i := 0; i < N; i++ { for k := 0; k <= sum; k++ { dp[i][0][k] = 0 } } for k := 0; k <= sum; k++ { if arr[0] <= k { dp[0][1][k] = arr[0] } else { dp[0][1][k] = INT_MIN } } for i := 1; i < N; i++ { for j := 1; j <= GetMin(i+1, M); j++ { for k := 0; k <= sum; k++ { dp[i][j][k] = dp[i-1][j][k] if k-arr[i] >= 0 { dp[i][j][k] = GetMax(dp[i][j][k], dp[i-1][j-1][k-arr[i]]+arr[i]) } } } } return GetMax(dp[N-1][M][sum], dp[N-1][N-M][sum])}func GetMin(a int, b int) int { if a < b { return a } else { return b }}func GetMax(a int, b int) int { if a > b { return a } else { return b }}执行后果如下：
左神java代码
评论