2023-07-02：给定一个 1~N 的排列，每次将相邻两数相加，可以得到新的序列，长度是 N-1 再对新的序列，每次将相邻两数相加，可以得到新的序列，长度是 N-2 这样下去可以最终只剩一个数字比如 :

作者：福大大架构师每日一题

2023-07-02
北京
本文字数：1706 字
阅读完需：约 6 分钟

2023-07-02：给定一个 1~N 的排列，每次将相邻两数相加，可以得到新的序列，长度是 N-1

再对新的序列，每次将相邻两数相加，可以得到新的序列，长度是 N-2

这样下去可以最终只剩一个数字

比如 :

3 1 2 4

4 3 6

7 9

现在如果知道 N，和最后的数字 sum，反推最原始的序列是什么

如果有多个答案，返回字典序最小的那个

字典序看做所有数字拼起来的字符串字典序

比如

1, 10, 2... 拼起来是 1102...

1, 2, 3, 4... 拼起来是 1234...

认为 1, 10, 2...的字典序更小

如果给定的 n 和 sum，有答案，返回一个 N 长度的答案数组

如果给定的 n 和 sum，无答案，返回一个 1 长度的数组{ -1 }

输入 : N = 4, sum = 16

输出 : 3 1 2 4

输入 : N = 10, sum = 4116

输出 : 1 3 5 7 10 9 8 6 4 2

答案 2023-07-02：

大体步骤如下：

1.创建一个二维动态数组dp，大小为(1<<(n+1))x(sums[n]+1)。

2.定义一个变量status，其初始值为((1 << (n + 1)) - 1) ^ 1。

3.如果n小于 1 或大于 10，或者sum大于sums[n]，则返回数组[-1]。

4.调用process函数处理状态status、剩余和rest、索引index、长度n、模数组modulus和动态数组dp，得到结果ans。

5.如果ans的值为-1，说明无法找到合适的序列，返回数组[-1]。

6.创建一个长度为n的答案数组ans，并初始化index为 0，rest为sum。

7.当status不等于 0 时，执行以下循环：

将dp[status][rest]的值赋给ans[index]。
将status异或上1 << ans[index]，更新status。
将rest减去ans[index] * modulus[index]，更新rest。
将index加 1。

8.返回答案数组ans。

总的时间复杂度：O(2^N * sum)，其中 N 为输入的 n，sum 为输入的 sum。总的空间复杂度：O(2^N * sum)，包括二维动态数组 dp 的空间。

go 语言代码如下：

package main
import "fmt"
var moduluses = [][]int{  {},  {1},  {1, 1},  {1, 2, 1},  {1, 3, 3, 1},  {1, 4, 6, 4, 1},  {1, 5, 10, 10, 5, 1},  {1, 6, 15, 20, 15, 6, 1},  {1, 7, 21, 35, 35, 21, 7, 1},  {1, 8, 28, 56, 70, 56, 28, 8, 1},  {1, 9, 36, 84, 126, 126, 84, 36, 9, 1},}
var sums = []int{0, 1, 3, 9, 24, 61, 148, 350, 808, 1837, 4116}
func lsp(n int, sum int) []int {  if n < 1 || n > 10 || sum > sums[n] {    return []int{-1}  }  dp := make([][]int, 1<<(n+1))  for i := range dp {    dp[i] = make([]int, sums[n]+1)  }  status := ((1 << (n + 1)) - 1) ^ 1  if !process(status, sum, 0, n, moduluses[n], dp) {    return []int{-1}  }  ans := make([]int, n)  index := 0  rest := sum  for status != 0 {    ans[index] = dp[status][rest]    status ^= 1 << ans[index]    rest -= ans[index] * moduluses[n][index]    index++  }  return ans}
func process(status int, rest int, index int, n int, modulus []int, dp [][]int) bool {  if rest < 0 {    return false  }  if status == 0 {    return rest == 0  }  if dp[status][rest] != 0 {    return dp[status][rest] != -1  }  ans := -1  if n == 10 && (status&(1<<10)) != 0 {    if process(status^(1<<10), rest-modulus[index]*10, index+1, n, modulus, dp) {      ans = 10    }  }  if ans == -1 {    for i := 1; i <= n; i++ {      if (status & (1 << i)) != 0 {        if process(status^(1<<i), rest-modulus[index]*i, index+1, n, modulus, dp) {          ans = i          break        }      }    }  }  dp[status][rest] = ans  return ans != -1}
func main() {  N1 := 4  sum1 := 16  ans1 := lsp(N1, sum1)  for _, num := range ans1 {    fmt.Printf("%d ", num)  }  fmt.Println()
  N2 := 10  sum2 := 4116  ans2 := lsp(N2, sum2)  for _, num := range ans2 {    fmt.Printf("%d ", num)  }  fmt.Println()
  N3 := 10  sum3 := 3688  ans3 := lsp(N3, sum3)  for _, num := range ans3 {    fmt.Printf("%d ", num)  }  fmt.Println()
  N4 := 10  sum4 := 4013  ans4 := lsp(N4, sum4)  for _, num := range ans4 {    fmt.Printf("%d ", num)  }  fmt.Println()}