2023-07-02：給定一個1~N的排列，每次將相鄰兩數(shù)相加，可以得到新的序列，長度是N-1
2023-07-02：給定一個1~N的排列，每次將相鄰兩數(shù)相加，可以得到新的序列，長度是N-1
再對新的序列，每次將相鄰兩數(shù)相加，可以得到新的序列，長度是N-2
這樣下去可以最終只剩一個數(shù)字
比如 :
3 1 2 4
4 3 6
7 9
16
現(xiàn)在如果知道N，和最后的數(shù)字sum，反推最原始的序列是什么
如果有多個答案，返回字典序最小的那個
字典序看做所有數(shù)字拼起來的字符串字典序
比如
1, 10, 2... 拼起來是 1102...
1, 2, 3, 4... 拼起來是 1234...
認為 1, 10, 2...的字典序更小
如果給定的n和sum，有答案，返回一個N長度的答案數(shù)組
如果給定的n和sum，無答案，返回一個1長度的數(shù)組{ -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.創(chuàng)建一個二維動態(tài)數(shù)組dp，大小為(1<<(n+1))x(sums[n]+1)。
2.定義一個變量status，其初始值為((1 << (n + 1)) - 1) ^ 1。
3.如果n小于1或大于10，或者sum大于sums[n]，則返回數(shù)組[-1]。
4.調(diào)用process函數(shù)處理狀態(tài)status、剩余和rest、索引index、長度n、模數(shù)組modulus和動態(tài)數(shù)組dp，得到結(jié)果ans。
5.如果ans的值為-1，說明無法找到合適的序列，返回數(shù)組[-1]。
6.創(chuàng)建一個長度為n的答案數(shù)組ans，并初始化index為0，rest為sum。
7.當status不等于0時，執(zhí)行以下循環(huán)：
??將
dp[status][rest]的值賦給ans[index]。??將
status異或上1 << ans[index]，更新status。??將
rest減去ans[index] * modulus[index]，更新rest。??將
index加1。
8.返回答案數(shù)組ans。
總的時間復(fù)雜度：O(2^N * sum)，其中N為輸入的n，sum為輸入的sum。 總的空間復(fù)雜度：O(2^N * sum)，包括二維動態(tài)數(shù)組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()
}
