🔗 🔴 3826. Minimum Partition Score

Problem Statement

題目簡述

給定陣列 nums 和整數 k，將 nums 恰好分成 k 個連續子陣列。每個子陣列的值定義為 sum⋅(sum+1)2\frac{sum \cdot (sum+1)}{2}，其中 sumsum 是該子陣列的元素和。求所有分割方式中，子陣列值總和的最小值。

Constraints

約束條件

  • 1≤n≤10001 \le n \le 1000
  • 1≤nums[i]≤1041 \le nums[i] \le 10^4
  • 1≤k≤n1 \le k \le n

思路：劃分型 DP → 斜率優化（凸包優化）

從暴力 DP 出發

本題是標準的劃分型 DP（約束劃分個數）。由於子陣列的值 sum⋅(sum+1)2\frac{sum \cdot (sum+1)}{2} 帶分母不好處理，我們先計算分子的和（即把每個子陣列的值乘以 22），最後再除以 22 輸出即可。

設前綴和陣列為 ss，其中 si=∑t=0i−1nums[t]s_i = \sum_{t=0}^{i-1} nums[t]（即前 ii 個元素的和）。

定義狀態：f[K][i]f[K][i] 表示把長度為 ii 的前綴 [0,i−1][0, i-1] 劃分成恰好 KK 個子陣列的最小分數（乘以 22）。

枚舉最後一段子陣列的左端點 jj（0≤j<i0 \le j < i），則：

f[K][i]=min⁡j=0i−1{f[K−1][j]+(si−sj)(si−sj+1)}f[K][i] = \min_{j=0}^{i-1} \left\{ f[K-1][j] + (s_i - s_j)(s_i - s_j + 1) \right\}

初始值 f[0][0]=0f[0][0] = 0，其餘 f[K][i]=∞f[K][i] = \infty。最終答案為 f[k][n]/2f[k][n] / 2。

直接做是 O(kn2)\mathcal{O}(kn^2)，對於 n≤1000n \le 1000 仍太慢，需要優化。

可復用模型：劃分型 DP

這類「恰好分成 kk 段」的 DP，常見套路是逐步增加分段數，用前一輪的結果計算當前輪。複雜度瓶頸在內層的 min⁡\min 枚舉，優化方向通常是斜率優化、決策單調性或資料結構。

方法一：斜率優化 DP（凸包 + 二分搜尋）

展開轉移式：發現內積形式

先從上面的暴力轉移式下手。對於固定的分段數與右端點，真正需要優化的是「枚舉最後一段左端點」這個 min⁡\min。

把轉移式展開：

f[K][i]=min⁡0≤j<i{f[K−1][j]+(si−sj)2+(si−sj)}=min⁡0≤j<i{f[K−1][j]+si2−2sisj+sj2+si−sj}=si2+si+min⁡0≤j<i{f[K−1][j]−2sisj+sj2−sj}\begin{aligned} f[K][i] &= \underset{0 \le j < i}{\min} \left\{ f[K-1][j] + (s_i - s_j)^2 + (s_i - s_j) \right\} \\[4pt] &= \underset{0 \le j < i}{\min} \left\{ f[K-1][j] + s_i^2 - 2s_i s_j + s_j^2 + s_i - s_j \right\} \\[4pt] &= s_i^2 + s_i + \underset{0 \le j < i}{\min} \left\{ f[K-1][j] - 2s_i s_j + s_j^2 - s_j \right\} \end{aligned}

其中 si2+sis_i^2+s_i 只和目前右端點有關，和左端點無關，可以先放到 min⁡\min 外面。剩下要最小化的部分，恰好可以寫成二維內積。

定義：

  • 候選點：vj=(sj,  f[K−1][j]+sj2−sj)v_j = \big(s_j,\; f[K-1][j] + s_j^2 - s_j\big)
  • 查詢向量：p=(−2si,  1)p = (-2s_i,\; 1)

則內層最小值為：

min⁡0≤j<i  p⋅vj\underset{0 \le j < i}{\min} \; p \cdot v_j

於是每一輪轉移變成：

f[K][i]=si2+si+min⁡0≤j<i  p⋅vjf[K][i] = s_i^2 + s_i + \underset{0 \le j < i}{\min} \; p \cdot v_j

這個變形是斜率優化的入口：原本是在所有左端點中暴力挑一個最小代數式，現在變成「在一組平面點中，找與查詢向量內積最小的點」。

為什麼要變成內積？

內積有明確的幾何意義：p⋅vp \cdot v 等於 vv 在 pp 方向上的投影長度乘以 ∣p∣|p|。對同一次查詢來說，∣p∣|p| 是定值，所以最小化內積等價於最小化投影長度。這讓我們可以從凸包的角度排除不可能成為最優決策的點。

凸包的幾何直覺

把候選點 {vj}\{v_j\} 畫在平面上。對於一個給定的查詢向量 pp，我們要找投影長度最小的點。

關鍵觀察

只有下凸包上的點才可能成為答案。凸包內部的點，其投影長度一定比某個凸包頂點更長（因為 pp 指向凸包外部方向時，內點的投影會被頂點「遮擋」）。

從凸包與內積的角度看，每個候選決策點都是平面上的一個點 vjv_j，每次轉移則是一個查詢向量 p=(−2si,1)p = (-2s_i, 1)。我們要做的事，不是逐一比較所有候選點，而是在這些點中找到讓內積 p⋅vjp \cdot v_j 最小的那一個。

對固定的查詢向量 pp，內積 p⋅vp \cdot v 可以理解成點 vv 在方向 pp 上的投影長度（再乘上一個固定倍數）。因此，凸包內部的點不可能比某個凸包頂點取得更小的投影值；真正可能成為答案的，只會是凸包邊界上的點。又因為我們要求的是最小值，所以只需要維護下凸包。

因此每一輪 DP，我們需要做兩件事：

  1. 維護下凸包：隨著 jj 增加，將新的候選點 vjv_j 加入凸包
  2. 在凸包上查詢：給定查詢向量 pp，找到使 p⋅vp \cdot v 最小的凸包頂點

維護凸包（Andrew 演算法）

由於 sjs_j（即 vjv_j 的 xx 座標）是單調遞增的，我們不需要排序，只需要在加入新點時檢查「是否破壞凸性」。

對於下凸包，依序考慮三個點 A,B,CA, B, C（依 xx 遞增）。外積（cross product）

AB→×BC→\overrightarrow{AB} \times \overrightarrow{BC}

可以判斷從邊 ABAB 轉向邊 BCBC 的方向：

  • 若外積 >0> 0，代表從 ABAB 到 BCBC 是逆時針轉向，也就是左轉，BB 在 ACAC 下方，仍可能是下凸包上的頂點，應保留。
  • 若外積 <0< 0，代表從 ABAB 到 BCBC 是順時針轉向，也就是右轉，BB 在 ACAC 上方，不可能出現在下凸包上，應彈出。
  • 若外積 =0= 0，三點共線。求最小值時，中間點不會比兩端點更優，也可以彈出。

因此維護下凸包時，只要滿足 AB→×BC→≤0\overrightarrow{AB} \times \overrightarrow{BC} \le 0，就把中間點 BB 刪掉；反之保留。

相同 xx 座標的處理

由於前綴和嚴格遞增（nums[i]≥1nums[i] \ge 1），不同 jj 的 sjs_j 必然不同，所以不會出現 xx 座標相同的情況。但若題目允許 00，則需要保留 yy 較小的那個（求 min⁡\min 時）。

在凸包上二分查詢

對固定的 pp，內積 p⋅vp \cdot v 在凸包頂點上先變小再變大（單峰函數）。因此可以二分找到最小的位置：

  • 取中間頂點 vmidv_{mid} 和 vmid+1v_{mid+1}
  • 若 p⋅vmid≥p⋅vmid+1p \cdot v_{mid} \ge p \cdot v_{mid+1}，說明還在下降段，最佳點在右邊
  • 否則在左邊

這樣每次查詢是 O(log⁡n)\mathcal{O}(\log n)。

邊界說明

ii 的列舉範圍是 [K,  n−(k−K)][K,\; n-(k-K)]，因為剩下的元素至少要能分給後面的 k−Kk-K 段，每段至少一個元素。

複雜度分析

  • 時間複雜度：O(knlog⁡n)\mathcal{O}(kn \log n) — 每輪有 O(n)\mathcal{O}(n) 個狀態，每次查詢 O(log⁡n)\mathcal{O}(\log n)
  • 空間複雜度：O(n)\mathcal{O}(n) — 兩層 DP 陣列 + 凸包

方法二：斜率優化 DP + 單調隊列查詢

為什麼可以去掉二分？

方法一已經把轉移變成了「維護下凸包 + 查詢最小內積」。如果查詢向量沒有額外性質，就用 query_bisect() 在凸包頂點上二分，單次查詢是 O(log⁡n)\mathcal{O}(\log n)。

但本題還有一個更強的性質：查詢向量本身是單調變化的。

因為所有元素都是正數，前綴和 sis_i 會隨著右端點增大而嚴格遞增。查詢向量

p=(−2si,  1)p = (-2s_i,\; 1)

的第一維 −2si-2s_i 因此會單調遞減，而第二維固定為 11。換句話說，當右端點往右走時，查詢向量的方向只會往同一側旋轉，不會反向。

這導致一個重要性質：

關鍵觀察：最優點單調右移

在下凸包頂點序列上，若某個頂點已經不再是當前查詢的最優點，那麼之後查詢向量繼續往同一方向旋轉時，它也不可能重新變回最優點。因此，最優頂點只會沿著凸包由左往右移動。

用內積來說，若目前查詢向量 pp 滿足

p⋅q0≥p⋅q1p \cdot q_0 \ge p \cdot q_1

代表隊首第一個點 q0q_0 已經不如下一個點 q1q_1。由於之後的查詢方向仍然單調旋轉，q0q_0 再也沒有機會成為最優決策，可以直接從隊首刪掉。

這樣就不需要每次二分了：隊首永遠維護成目前查詢的最優點，查詢均攤 O(1)\mathcal{O}(1)。

可復用模型：同一個凸包，換查詢方式

add() 的維護邏輯仍然是方法一的下凸包維護。差別只在查詢：一般情況用 query_bisect()，如果能證明最佳點只會往右移動，就可以改用 query_mono()，用單調隊列把查詢降到均攤 O(1)\mathcal{O}(1)。

query_mono() 如何工作？

ConvexHull 裡的 hull 本來就是按照 xx 座標遞增存放的下凸包頂點。方法二不需要重寫一套凸包，只需要在查詢時把已經過期的隊首彈掉。

對目前的查詢向量 pp，若隊首兩個點 q0,q1q_0,q_1 滿足：

p⋅q0≥p⋅q1p \cdot q_0 \ge p \cdot q_1

表示 q0q_0 已經不比 q1q_1 優。由於後面的查詢方向仍然單調旋轉，最佳點只會往右移動，所以 q0q_0 可以永久刪除。重複這個過程後，隊首就是目前查詢的最優點。

因此，方法二的本質不是重寫凸包，而是在同一個凸包結構上，把查詢函式從二分查詢換成單調隊列查詢。其餘建點方式、add() 的凸包維護、DP 轉移式都和方法一相同。

注意：query_mono() 不能亂用

方法二額外依賴「最佳點索引單調右移」。如果查詢向量不單調，隊首被彈出後可能之後又變成最優點，這時就必須改回 query_bisect()。

複雜度分析

  • 時間複雜度：O(kn)\mathcal{O}(kn) — 每輪每個點最多進隊一次、出隊一次，每次查詢均攤 O(1)\mathcal{O}(1)
  • 空間複雜度：O(n)\mathcal{O}(n) — 與方法一相同
方法二 vs 方法一

對於 n=1000n=1000 的範圍，方法一（O(knlog⁡n)\mathcal{O}(kn\log n)）和方法二（O(kn)\mathcal{O}(kn)）都能通過。方法一的好處是通用性強——即使查詢向量不單調（例如 numsnums 中有負數），凸包 + 二分仍然有效。方法二更快但要求查詢向量具有單調性。

方法三：分治法優化 DP（決策單調性）

序列分割 DP 的通用形式

除了斜率優化，這題也可以套用另一個經典模板：決策單調性優化 DP。

對於形如

dp[K][j]=min⁡0≤i<j{dp[K−1][i]+w(i,j)}dp[K][j] = \min_{0 \le i < j}\{dp[K-1][i] + w(i, j)\}

的序列分割問題，如果區間代價函數 w(i,j)w(i,j) 滿足四邊形不等式（Quadrangle Inequality），也就是對所有 a≤b≤c≤da \le b \le c \le d，都有

w(a,c)+w(b,d)≤w(a,d)+w(b,c)w(a, c) + w(b, d) \le w(a, d) + w(b, c)

那麼這個轉移通常會具有決策單調性。設 opt[K][j]opt[K][j] 表示 dp[K][j]dp[K][j] 取得最小值時的最優決策點，則有：

opt[K][j]≤opt[K][j+1]opt[K][j] \le opt[K][j+1]

也就是說，同一層 KK 裡，右端點 jj 越往右，最優切分點不會往左退。

可復用模型：只換代價函數

很多序列分割題都長這樣。DP 形式不變，分治優化模板也不變，真正需要替換的通常只有區間代價函數 w(i,j)w(i,j)。

套到本題

本題的區間 [i,j)[i,j) 代價為：

w(i,j)=(sj−si)(sj−si+1)2w(i,j)=\frac{(s_j-s_i)(s_j-s_i+1)}{2}

其中 ss 是前綴和。因為 nums[t]>0nums[t] > 0，區間和會隨著右端點增加而增加，而這個代價函數滿足四邊形不等式，所以本題同樣具有決策單調性。

於是原本每個狀態都枚舉所有 i<ji<j 的暴力轉移：

dp[K][j]=min⁡0≤i<j{dp[K−1][i]+w(i,j)}dp[K][j] = \min_{0 \le i < j}\{dp[K-1][i] + w(i,j)\}

可以改成：在計算同一層 KK 時，不再從左到右逐格暴力枚舉，而是用分治一次處理一整段狀態。

為什麼可以用分治？

先看同一層 DP 要做什麼。上一層狀態已經固定，現在每個右端點都是一個獨立的最小化問題：在所有合法切分點中，找出讓「上一層答案 + 最後一段代價」最小的位置。

暴力做法會對每個右端點都重新枚舉所有切分點，所以一層是 O(n2)\mathcal{O}(n^2)。要優化，關鍵不是改變轉移式，而是縮小每個右端點需要枚舉的切分點範圍。

四邊形不等式給出的正是這個範圍資訊。它保證同一層中右端點越往右，最優切分點不會往左退。換句話說，如果把所有右端點按順序排成一列，它們的最優決策也是一個單調不降的序列。

核心想法：先算中點，再切決策範圍

對一段連續狀態，如果先算出中點的最優決策，那麼左半段的答案一定不會用到比它更右的決策，右半段的答案一定不會用到比它更左的決策。這就把「狀態區間」和「決策區間」同時切成了兩半。

具體來說，假設目前要計算一段右端點 [l,r][l,r]，並且已知這整段的最優切分點只可能落在 [optl,optr][opt_l,opt_r]。取中點 midmid，暴力掃描 [optl,optr][opt_l,opt_r] 中對 midmid 合法的切分點，得到最優決策 optopt。

由決策單調性可知：

  • 對於左半段 [l,mid−1][l,mid-1]，右端點都小於 midmid，所以最優決策不會超過 optopt，決策範圍可縮成 [optl,opt][opt_l,opt]。
  • 對於右半段 [mid+1,r][mid+1,r]，右端點都大於 midmid，所以最優決策不會小於 optopt，決策範圍可縮成 [opt,optr][opt,opt_r]。

然後對左右兩段遞迴做同樣的事。這就是分治 DP 優化：每次只完整求中點，但中點的最優決策會成為左右子問題的新邊界。

為什麼不會錯過答案？

分治看起來像是在「只算中點，然後丟掉一半決策」，所以最需要確認的是：被丟掉的決策真的不可能成為答案。

為什麼不會錯過答案？（正確性證明）

這裡維護的是一個不變量：每次遞迴處理一段右端點 [l,r][l,r] 時，傳進來的決策範圍 [optl,optr][opt_l,opt_r] 一定包含這整段所有狀態的最優決策。只要這個不變量成立，計算中點時在這個範圍內暴力枚舉，就一定能找到中點的真正最優決策。

算出中點的最優決策 optopt 之後，決策單調性告訴我們：

x<mid⇒opt[x]≤opt[mid]=optx < mid \Rightarrow opt[x] \le opt[mid] = opt

所以左半段的最優決策不可能在 optopt 右邊。既然原本已知它們都在 [optl,optr][opt_l,opt_r]，那麼左半段真正需要保留的範圍就是 [optl,opt][opt_l,opt]，右邊那部分不可能用到，刪掉不會漏答案。

同理，對右半段有：

x>mid⇒opt[x]≥opt[mid]=optx > mid \Rightarrow opt[x] \ge opt[mid] = opt

所以右半段的最優決策不可能在 optopt 左邊，範圍可以縮成 [opt,optr][opt,opt_r]。

正確性的核心：

分治不是憑感覺剪枝，而是在維護「答案一定還在傳入的決策區間內」這個不變量。中點的最優決策只是把這個保證傳給左右子問題：左邊答案不會越過它往右，右邊答案不會越過它往左。

從最外層開始，所有合法切分點本來就都包含在初始範圍內；每往下一層遞迴，縮小後的範圍仍然包含該子區間的所有最優決策。因此遞迴到每一個狀態時，它都會在包含真正答案的範圍中枚舉，自然不會錯過最優解。

狀態覆蓋的完整性

雖然分治每次只暴力計算中點 midmid 的最優決策，但隨著遞迴不斷向下分裂，狀態區間 [l,r][l, r] 會被細分到 l=rl = r 的葉子節點。因此，分治過程最終會計算完所有的 nf[i]nf[i]（即所有狀態的最優值都會被填滿），不會遺漏任何一個狀態。

實作細節：合法切分點的邊界

由於最後一段必須非空，切分點 pp 必須小於右端點 midmid（即 p≤mid−1p \le mid-1）。

結合分治傳下來的決策範圍 [optl,optr][opt_l, opt_r]，實際枚舉範圍應為 p∈[optl,  min⁡(optr,mid−1)]p \in [opt_l,\; \min(opt_r, mid-1)]。這也是為什麼程式碼中要寫成 min(opt_r, mid - 1)，以避免將空區間或反向區間算入。

複雜度分析

複雜度細節推導

分治樹有 O(log⁡n)\mathcal{O}(\log n) 層。每一層中，不同節點負責的是互不重疊的狀態區間；而由於決策範圍會被中點的最優決策切開，同一層要掃描的候選決策總量可以控制在 O(n)\mathcal{O}(n) 級別。

所以，單層 DP 的計算量從暴力的 O(n2)\mathcal{O}(n^2) 成功降為 O(nlog⁡n)\mathcal{O}(n\log n)。外面還要跑 kk 層分段數，總時間就是 O(knlog⁡n)\mathcal{O}(kn\log n)。

  • 時間複雜度：O(knlog⁡n)\mathcal{O}(kn \log n) — 每一輪分治樹的深度為 O(log⁡n)\mathcal{O}(\log n)，每一層的決策點枚舉總和為 O(n)\mathcal{O}(n)。
  • 空間複雜度：O(n)\mathcal{O}(n) — 僅需滾動陣列維護 DP 狀態。

類題

斜率優化DP

決策單調性優化DP

决策单调性优化 DP 的一些参考资料 & wqs 二分 O(NlogNlogV)

參考資料

對於斜率優化DP的部分，強烈推薦搭配靈神的週賽講解影片學習。

參考資料

Code

方法一：斜率優化DP（凸包 + 二分搜尋）& 方法二：單調隊列優化

ConvexHull 的兩種查詢方式

下面的 ConvexHull 同時支援兩種查詢方式：query_bisect() 是通用寫法，不要求查詢向量單調；query_mono() 則用在最佳點只會往右移動的情況，可以用單調隊列維護，均攤 O(1)\mathcal{O}(1) 查詢。

方法一使用：

1
best = cht.query_bisect(p)

方法二只需要改成：

1
best = cht.query_mono(p)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
class Vec:
    __slots__ = "x", "y"

    def __init__(self, x: int, y: int):
        self.x = x
        self.y = y

    def __add__(self, b: "Vec") -> "Vec":
        return Vec(self.x + b.x, self.y + b.y)

    def __sub__(self, b: "Vec") -> "Vec":
        return Vec(self.x - b.x, self.y - b.y)

    def det(self, b: "Vec") -> int:
        return self.x * b.y - self.y * b.x

    def dot(self, b: "Vec") -> int:
        return self.x * b.x + self.y * b.y


class ConvexHull:
    """
    注意：
    - add() 的點需要依 x 遞增加入。
    - query_bisect() 不要求查詢向量單調，使用二分搜尋。
    - query_mono() 使用單調隊列優化，因此查詢向量 p 需要滿足最佳點索引單調往前移動。
    - 若查詢不具單調性，請使用 ConvexHull 的二分 query()。
    """

    def __init__(self):
        self.hull = deque()  # min 維護下凸包

    def _bad(self, a: Vec, b: Vec, c: Vec) -> bool:
        # 順時針方向或共線，此時 b 點不會是「下凸包」的一部分
        return (b - a).det(c - b) <= 0

    def add(self, v: Vec) -> None:
        hull = self.hull

        # 如果新點與最後一個點 x 相同，只保留對應 mode 下較優的 y
        if hull and hull[-1].x == v.x:
            if hull[-1].y <= v.y:
                return
            hull.pop()

        # 維護凸包性質，移除不可能成為凸包的中間點
        while len(hull) >= 2 and self._bad(hull[-2], hull[-1], v):
            hull.pop()

        hull.append(v)

    def query_bisect(self, p: Vec) -> int:
        hull = self.hull

        # 使用二分搜尋找到最佳點
        left, right = 0, len(hull) - 2
        while left <= right:
            mid = (left + right) // 2
            curr = p.dot(hull[mid])
            nxxt = p.dot(hull[mid + 1])
            if curr >= nxxt:
                left = mid + 1
            else:
                right = mid - 1

        return p.dot(hull[left])

    def query_mono(self, p: Vec) -> int:
        hull = self.hull

        # 使用單調隊列維護
        while len(hull) >= 2 and p.dot(hull[0]) >= p.dot(hull[1]):
            hull.popleft()
        return p.dot(hull[0])


class Solution:
    def minPartitionScore(self, nums: List[int], k: int) -> int:
        n = len(nums)
        pre = list(accumulate(nums, initial=0))

        f = [inf] * (n + 1)
        f[0] = 0

        for K in range(1, k + 1):
            nf = [inf] * (n + 1)
            cht = ConvexHull()

            s = pre[K - 1]
            cht.add(Vec(s, f[K - 1] + s * s - s))

            max_i = n - (k - K)
            for i in range(K, max_i + 1):
                s = pre[i]
                p = Vec(-2 * s, 1)

                # best = cht.query_bisect(p)
                best = cht.query_mono(p)  # 單調隊列優化
                nf[i] = best + s * s + s

                if f[i] < inf:
                    cht.add(Vec(s, f[i] + s * s - s))
            f = nf

        return f[n] // 2

方法三：分治法優化 DP（決策單調性）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def minPartitionScore(self, nums: List[int], k: int) -> int:
        n = len(nums)
        s = list(accumulate(nums, initial=0))

        def cost(l: int, r: int) -> int:  # cost of [l, r)
            v = s[r] - s[l]
            return v * (v + 1) // 2

        f = [float('inf')] * (n + 1)
        nf = [float('inf')] * (n + 1)
        f[0] = 0

        def solve(l: int, r: int, opt_l: int, opt_r: int):
            if l > r:
                return
            mid = (l + r) // 2

            best_val = float("inf")
            opt = -1  # opt[mid]
            for p in range(opt_l, min(opt_r, mid - 1) + 1):
                val = f[p] + cost(p, mid)
                if val < best_val:
                    best_val = val
                    opt = p
            nf[mid] = best_val

            solve(l, mid - 1, opt_l, opt)  # 左側的決策點一定 <= opt[mid]
            solve(mid + 1, r, opt, opt_r)  # 右側的決策點一定 >= opt[mid]

        for j in range(1, k + 1):
            solve(j, n, j - 1, n - 1)  # 在 D&C 的過程中計算 nf
            f = nf.copy()
        return f[n]