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

moonfdd 的个人博客 / 10 / 0 / 创建于 9个月前

再对新的序列，每次将相邻两数相加，可以得到新的序列，长度是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()
}