2023-07-02：给定一个1~N的排列，每次将相邻两数相加，可以得到新的序列，长度是N-1
再对新的序列，每次将相邻两数相加，可以得到新的序列，长度是N-2
这样下去可以最终只剩一个数字
比如 :
3 1 2 4
4 3 6
7 9
16
现在如果知道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，大小为(1x(sums[n]+1)。
2.定义一个变量status，其初始值为((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 ，更新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 10 || sum > sums[n] {
return []int{-1}
}
dp := make([][]int, 1
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
源创会，线下重启！2023年7月1日深圳站—基础软件技术面面谈！免费票限时抢购！ 文章目录 问题描述 问题现象 告警 单SQL性能慢分析 步骤一：确定目标SQL 步骤二：收集统计信息、提前排除影响 步骤三：分析SQL性能瓶颈 单SQL性能慢-视图分析 流控导致…
