V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Stone Merging

Fill an interval-DP triangle by trying every final split and adding the sum of the merged interval.

Core idea

The final operation on interval i through j must merge two adjacent already-complete subintervals. Try every split point and add the fixed total weight of the interval.

Read the visualization

The upper-triangular table fills by increasing interval length. Each highlighted cell compares split candidates from two smaller cells plus a prefix-sum interval cost.

4132
40
10
30
20

Initialize every one-pile interval with zero merge cost.

1function stoneMerge(a: number[]): number {
2 const n = a.length;
3 const pre = [0];
4 for (const x of a) pre.push(pre[pre.length - 1] + x);
5 const dp = Array.from({ length: n }, () => new Array(n).fill(0));
6 for (let len = 2; len <= n; len++) // interval pair length
7 for (let i = 0; i + len - 1 < n; i++) {
8 const j = i + len - 1;
9 dp[i][j] = Infinity;
10 for (let k = i; k < j; k++) // split partition point
11 dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
12 dp[i][j] += pre[j + 1] - pre[i]; // current times merge cost = interval sum
13 }
14 return dp[0][n - 1];
15}
stone piles[4, 1, 3, 2]
1 / 8

Complexity and tradeoffs

Time: O(n^3). Space: O(n^2). Each interval considers all split points; prefix sums make its merge cost O(1).

Invariant: Before intervals of length L are processed, every shorter interval already stores its minimum merge cost.

Where it fits

Interval DP appears in matrix-chain multiplication, polygon triangulation, optimal parsing, and burst-style games. Faster optimizations require additional structure in the split costs.