Funcia
Lv.4dpinterval-dpknuth-optimization

Merging Chapters at Minimum Cost

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

A novel is stored as N chapter files in a fixed order; file i has size sizes[i]. You may merge two adjacent files into one, which costs the sum of their sizes (the merged file has that size too). Return the minimum total cost to end up with a single file.

Examples

sizesresult
[40, 30, 30, 50]300
[1, 100, 1]203
[7]0

Example 1 — merge 40+30 and 30+50, then the two halves: 70+80+150=30070 + 80 + 150 = 300 (starting in the middle costs 310).

Example 2 — the two 1s are not adjacent, so 101+102=203101 + 102 = 203.

Example 3 — nothing to merge.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(sizes: int[]) → long

Constraints

  • 1≤N=1 \le N = sizes.length ≤3,000\le 3{,}000
  • 1≤1 \le sizes[i] ≤1,000,000\le 1{,}000{,}000
  • The answer may not fit in 32 bits.

Expected complexity

Time
O(N^2)
Space
O(N^2)

Examples

sizesExpected
[40,30,30,50]300
[1,100,1]203
[7]0

Hint

Hint

The interval DP dp[i][j] = min_k (dp[i][k] + dp[k+1][j]) + S(i, j) is O(N3)O(N^3). Because the range-sum cost satisfies the quadrangle inequality and is monotone, Knuth's optimization applies: the best split satisfies opt[i][j-1] <= opt[i][j] <= opt[i+1][j], so only that range of k needs to be scanned, and the scans telescope to O(N2)O(N^2) in total. Trying every k exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)236 msestimated
C++ (GCC, gnu++23)236 msderived
Python 3.134714 msderived
Java 251200 msderived
Kotlin 2.4 (JVM)1472 msestimated
C# 14 (.NET 10)1472 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.