On this page

Partition DP

You have a row of books of different thicknesses and shelves. The books must stay in order: the first few go on shelf 1, the next few on shelf 2, and so on. How do you split them so that the fullest shelf is as empty as possible?

You have a paragraph of words and a line width. Each line holds a run of consecutive words. Where do you break the lines so that the paragraph looks even, with no line ending in a big ugly gap?

You have a string and want to cut it into pieces that are all palindromes, using as few cuts as possible.

All three are partition DP: the input is a sequence, the output is a way to cut it into contiguous groups (blocks, segments, lines, shelves), each group has a cost that depends only on where it starts and ends, and the total is a sum (or max) of group costs. The DP state is always "the first elements have been grouped", optionally with "using exactly groups", and the transition is always the same question: where does the last group start?

This lesson sits between Interval DP and the optimisation tricks of DP Optimizations. Interval DP cut a range into two pieces at every level, recursively; partition DP cuts a prefix into "everything before" plus "one last group", which is simpler ( or instead of ) and, more importantly, has structure that the optimisation tricks can exploit. It also has a famous non-DP alternative for one important case: binary search on the answer.

Why this exists

Splitting ordered data into contiguous chunks is everywhere: lines of text, pages of a document, shards of a sorted key space, batches of a job queue, buckets of a histogram, segments of a time series. The order cannot change (you cannot move a word to another paragraph, or a key to a shard out of range order), so the only freedom is where to cut.

With elements there are gaps, and each gap is cut or not: ways to split. With exactly groups there are ways, which for and is about . Brute force is out.

Richard Bellman's 1961 note "On the approximation of curves by line segments using dynamic programming" (CACM 4(6)) already used exactly this DP: fit a curve with straight segments by asking where the last segment begins. Knuth and Plass applied it to line breaking in TeX (1981). Database researchers use it to build "V-optimal" histograms (Jagadish et al., 1998), and statisticians use it for exact one-dimensional -means clustering (Wang and Song, 2011) and for the "natural breaks" classification in map-making software. The same few lines of DP serve all of them.

Pattern triggers

If the problem says or has…Think of…
"split the array into (non-empty) contiguous subarrays"dp[g][i] over (groups used, prefix length)
"minimise the largest group sum", "painters", "ship within D days", "allocate books"Split array largest sum: DP, or binary search on the answer with a greedy check
"split into any number of pieces, each piece must be valid (palindrome, dictionary word, ≤ k long)"1-D dp[i] over prefixes: fewest pieces or count of ways
"break text into lines of width W, minimise raggedness"Word wrap: dp[i] over word positions, cost
"minimise the sum of (group cost)" with group cost = square, variance, max × lengthdp[g][i] = min_j dp[g-1][j] + cost(j, i)
"maximise the sum of averages / medians / maxima of the groups"Same template with max
"each group pays a fixed penalty plus its own cost"Unlimited groups, dp[i] = min_j dp[j] + cost(j, i) + C
up to with groups and a "nice" cost is too slow: divide-and-conquer optimisation, convex hull trick, or the Aliens trick
Groups need not be contiguous ("split into k subsets with equal sum")Not partition DP: that is subset / bitmask DP (Bitmask DP)

The meta-trigger: order is fixed, you choose cut points, and each group's cost depends only on its own two ends. If a group's cost depends on its neighbours, or groups can be non-contiguous, this template does not apply as is.

Intuition & first principles

The "last group" question

Take a = [7, 2, 5, 10, 8] and groups. Any split into two contiguous groups looks like a[0..j-1] | a[j..4]. The question "what is the best split of the first 5 elements into 2 groups?" becomes: for each possible start of the last group, what is the best split of the first elements into 1 group, and what does the last group cost?

Generalise. Let dp[g][i] = the best value for splitting the first elements (a[0..i-1]) into exactly non-empty groups. The last group is a[j..i-1] for some ; everything before it, a[0..j-1], is split into groups:

  • For "minimise the total cost", combine is + and best is min.
  • For "minimise the largest group", combine is max and best is min.
  • For "maximise the sum of averages", combine is + and best is max.

Base: dp[0][0] is the neutral value (0 for sums and maxima of non-negative numbers), and dp[0][i > 0] is impossible (you cannot split something into zero groups). The lower bound makes sure the first elements can hold non-empty groups.

graph LR
    P["dp[g-1][j]: first j elements in g-1 groups"] -->|"+ cost of a[j..i-1]"| C["dp[g][i]"]
    P2["dp[g-1][j']: another start j'"] -->|"+ cost of a[j'..i-1]"| C
    P3["..."] --> C

Unlimited groups: one dimension fewer

When there is no fixed ("as few pieces as possible", "any number of lines"), drop the group dimension:

Word break (in String DP) is this with cost = 0 and allowed = in dictionary. Palindrome partitioning is this with cost = 1 per piece and allowed = palindrome. Word wrap is this with cost = (W - width)² and allowed = fits on a line.

Making cost(j, i) cheap

The DP does or lookups of cost(j, i). If each lookup takes , everything slows by a factor of . So precompute:

  • Sums with prefix sums: sum(j, i) = pre[i] - pre[j], .
  • Line widths: same, with word lengths plus spaces.
  • Is it a palindrome? An interval table pal[j][i], once (see Interval DP).
  • Max of the group: extend the group one element at a time inside the loop, going leftwards from , and keep a running max.

The four questions for every partition DP

  1. Is the number of groups fixed? Yes → dp[g][i]. No → dp[i].
  2. How do group costs combine? Sum, max, or something else? (This decides whether binary search on the answer is an option.)
  3. What does one group cost, and can it be computed in ?
  4. How do you recover the cut points? Store the best for each cell and walk back from dp[k][n].

Mechanics

1. Split array largest sum (painter's partition), by DP

Problem (LeetCode 410). Split a into exactly non-empty contiguous groups; minimise the largest group sum. Also known as the painter's partition problem ( painters, boards of given lengths, each painter paints a contiguous run, minimise the time of the slowest painter), "allocate books", and "linear partition" (Skiena, The Algorithm Design Manual, the "Partition Problem" section of the dynamic programming chapter).

State: dp[g][i] = smallest possible "largest group sum" when a[0..i-1] is split into groups. Transition: dp[g][i] = min over j of max(dp[g-1][j], pre[i] - pre[j]). Answer: dp[k][n].

Example: a = [7, 2, 5, 10, 8], . Prefix sums pre = [0, 7, 9, 14, 24, 32].

Row is just the prefix sums: one group holding everything. Row :

CellLast group options a[j..i-1]max(dp[1][j], last sum)dp
dp[2][2]j=1: [2]max(7, 2) = 77
dp[2][3]j=1: [2,5]; j=2: [5]max(7, 7) = 7; max(9, 5) = 97
dp[2][4]j=1: [2,5,10]; j=2: [5,10]; j=3: [10]17; 15; max(14, 10) = 1414
dp[2][5]j=1: [2,5,10,8]; j=2: [5,10,8]; j=3: [10,8]; j=4: [8]25; 23; max(14, 18) = 18; max(24, 8) = 2418

The full table:

         i=0   1   2   3   4   5
g=0        0   -   -   -   -   -
g=1        -   7   9  14  24  32
g=2        -   -   7   7  14  18

Answer 18: [7, 2, 5] | [10, 8], group sums 14 and 18. The cut point came from j = 3 in dp[2][5]; walking back, dp[1][3] is a single group. With the answer drops to 14 ([7, 2, 5] | [10] | [8]).

Cost: rows × cells × up to choices of = time, space (or with two rows if you do not need the cuts).

2. Split array largest sum, by binary search on the answer

The DP works, but is for . A completely different idea is much faster.

Flip the question. Instead of "what is the smallest possible maximum?", ask "can we split into at most groups so that every group sum is at most ?" Call this feasible(C).

  • feasible(C) is easy: walk left to right, add each element to the current group while the sum stays , and start a new group when it would exceed . Count the groups. (If any single element exceeds , it is infeasible.) This greedy is optimal for the yes/no question: closing a group as late as possible never hurts, because the next group then starts later and has less to hold.
  • feasible is monotone: if a cap of works, any larger cap works too (the same split is still valid). So the answers look like F F F … F T T T … T as grows, and we want the first T. That is exactly the "lower bound on a monotone predicate" pattern from Binary Search.
  • The answer lies in [max(a), sum(a)]: no group can be smaller than the largest element, and one group holding everything is always enough.
  • "At most " vs "exactly ": if a split into fewer than groups works, splitting any group with 2+ elements further never increases the max, so exactly also works whenever .

Trace on [7, 2, 5, 10, 8], , range [10, 32]:

lohimidGreedy groups under cap midGroupsFeasible?Next
103221[7,2,5] [10,8]2yeshi = 21
102115[7,2,5] [10] [8]3nolo = 16
162118[7,2,5] [10,8]2yeshi = 18
161817[7,2,5] [10] [8]3nolo = 18

lo == hi == 18. Same answer, after 4 checks of each. In general where $S = $ sum(a): for and values up to , that is about steps.

flowchart TD
    A["lo = max(a), hi = sum(a)"] --> B{"lo < hi?"}
    B -->|"no"| R["answer = lo"]
    B -->|"yes"| M["mid = (lo + hi) // 2"]
    M --> G["greedy: count groups with every sum at most mid"]
    G --> F{"groups at most k?"}
    F -->|"yes: mid is enough"| H["hi = mid"]
    F -->|"no: mid is too small"| L["lo = mid + 1"]
    H --> B
    L --> B

When does binary search on the answer apply? Only when the objective is a bottleneck (minimise the maximum, maximise the minimum) and a greedy can answer the yes/no version. For "minimise the sum of squared group sums" there is no such check, and you need the DP (with optimisations).

DPBinary search on the answer
Time
Works forany group cost, any combinebottleneck objectives with a greedy feasibility test
Needsnothing specialmonotone predicate, non-negative values for the greedy
Gives the cut pointsyes, by walking backyes, by re-running the greedy at the answer
Handles negative numbersyesthe simple greedy breaks (a later negative can rescue a group)

3. Palindrome partitioning (unlimited groups)

Cut s into the fewest palindromic pieces. With pal[j][i] precomputed:

and the minimum number of cuts is pieces[n] - 1. For aab: pieces = [0, 1, 1, 2] (aa | b), 1 cut. This is the dp[i] template with cost 1 per piece; String DP has the full walkthrough, an -memory variant that expands palindromes around centres, and code in four languages, so it is not repeated here.

Its harder sibling, Palindrome Partitioning III (change the fewest letters so the string splits into exactly palindromes), is the fixed- template: cost(j, i) = letters to change to make s[j..i-1] a palindrome (an interval table), and dp[g][i] = min dp[g-1][j] + cost(j, i). This "interval table feeds a partition DP" combination is extremely common.

4. Word wrap: minimum raggedness

Problem. Words of lengths ; line width . Each line holds consecutive words separated by single spaces, so words on one line have width , which must be . A line with width has slack . Minimise the sum of squared slacks over all lines except the last (a short last line is normal and should not be punished).

Why squares? With plain sums, the total slack is the same for every layout that uses the same number of lines (total slack = lines × W − total width), so it cannot tell an even paragraph from a ragged one. Squaring punishes one huge gap more than several small ones, which is what eyes notice.

State: it is convenient to go from the back: dp[i] = minimum cost to lay out words , where word starts a line. dp[n] = 0. Transition: the line starting at word ends just before word (, as long as it fits):

The factor makes the last line free. Filling from the back makes "last line" simply "".

Example: words aaa bb cc ddddd (lengths 3, 2, 2, 5), .

iLine options starting at word iCostdp[i]
4(end)—0
3ddddd (last line, free)0 + dp[4] = 00
2cc → slack 4, 16 + dp[3]; cc ddddd is 8 wide, does not fit1616
1bb → 16 + dp[2] = 32; bb cc (width 5, slack 1) → 1 + dp[3] = 1min(32, 1)1
0aaa → 9 + dp[1] = 10; aaa bb (width 6, slack 0) → 0 + dp[2] = 16min(10, 16)10

Optimal layout (cost 10):

aaa       (slack 3, cost 9)
bb cc     (slack 1, cost 1)
ddddd     (last line, free)

The greedy layout (put as many words as fit on each line, the method used by most simple text editors) gives:

aaa bb    (slack 0, cost 0)
cc        (slack 4, cost 16)
ddddd     (last line, free)

Cost 16. Greedy minimises the number of lines, not raggedness: filling the first line perfectly leaves cc stranded. The DP looks ahead.

graph LR
    W0["word 0: aaa"] -->|"line aaa, cost 9"| W1["word 1: bb"]
    W0 -->|"line aaa bb, cost 0"| W2["word 2: cc"]
    W1 -->|"line bb, cost 16"| W2
    W1 -->|"line bb cc, cost 1"| W3["word 3: ddddd"]
    W2 -->|"line cc, cost 16"| W3
    W3 -->|"last line, free"| E["end"]

Seen this way, word wrap is a shortest path in a DAG: nodes are "a line starts at word ", edges are possible lines, weights are line costs. The DP is that shortest path computed in reverse topological order (see Topological Sort). The optimal path here is aaa (9) → bb cc (1) → ddddd (0).

Knuth–Plass. TeX's line breaker (Knuth and Plass, "Breaking Paragraphs into Lines", Software: Practice and Experience, 1981) is this DP with a richer model: "boxes" (words), "glue" (stretchable and shrinkable spaces), and "penalties" (places where breaking is allowed at a cost, such as hyphenation points). Each line gets a badness based on how much its glue had to stretch, then demerits plus extra charges for things like two hyphenated lines in a row or a very tight line next to a very loose one. To keep it fast, it only tracks "active" breakpoints that could still start a feasible line, which makes it close to linear in practice. Text justification on LeetCode (problem 68) is different: it fixes the greedy line breaks and asks you to distribute spaces, which is formatting, not optimisation.

5. Minimise the sum of squared group sums

Problem. Split a into contiguous groups, minimising . This rewards balanced groups (by convexity, equal sums would be ideal), and it is the core of 1-D -means, V-optimal histograms and load balancing with quadratic penalties.

For a = [1, 2, 3, 4, 5, 6] (total 21) and , perfectly equal groups would each sum to 7 (cost 147), but no contiguous split achieves that. The DP finds [1, 2, 3] | [4, 5] | [6] with sums 6, 9, 6: .

Here binary search on the answer does not work (the objective is a sum), so the DP is the tool. And at , it is slow for large . That is where the next section comes in.

6. Partition into groups with maximum average sum

Problem (LeetCode 813, "Largest Sum of Averages"). Split into at most non-empty contiguous groups and maximise the sum of the groups' averages. Same template, max instead of min, group cost = (pre[i] - pre[j]) / (i - j).

For [9, 1, 2, 3, 9] and : [9] | [1, 2, 3] | [9] scores . For non-negative numbers, more groups never hurt (splitting a group into two can only raise the sum of averages: the two averages straddle the old one and are each counted once), so "at most " equals "exactly " when .

def largest_sum_of_averages(a, k):
    n = len(a)
    pre = [0]
    for x in a:
        pre.append(pre[-1] + x)
    NEG = float("-inf")
    dp = [[NEG] * (n + 1) for _ in range(k + 1)]
    dp[0][0] = 0.0
    for g in range(1, k + 1):
        for i in range(g, n + 1):
            for j in range(g - 1, i):               # last group is a[j..i-1]
                if dp[g - 1][j] > NEG:
                    dp[g][i] = max(dp[g][i], dp[g - 1][j] + (pre[i] - pre[j]) / (i - j))
    return max(dp[g][n] for g in range(1, k + 1))


assert abs(largest_sum_of_averages([9, 1, 2, 3, 9], 3) - 20.0) < 1e-9
assert abs(largest_sum_of_averages([1, 2, 3, 4, 5, 6, 7], 4) - 20.5) < 1e-9
assert abs(largest_sum_of_averages([5], 1) - 5.0) < 1e-9

7. From O(k n²) to O(k n log n): divide and conquer optimisation

Look at where the best last-group start lands. For the sum-of-squares problem on [1, 2, 3, 4, 5, 6], let opt[g][i] = the best for dp[g][i]. For and the optimal starts are . In general, for many "nice" costs:

In words: if the prefix gets longer, the last group's best start never moves left. This monotonicity holds when the cost satisfies the quadrangle inequality ( for ), which squared range sums, 1-D -means within-cluster variance and many others do.

Divide and conquer. To fill row for all in [lo, hi], knowing the answer's lies in [optLo, optHi]:

  1. Compute the middle cell mid = (lo + hi) // 2 by trying every in [optLo, min(mid - 1, optHi)]. Call the best one best.
  2. Recurse on the left half [lo, mid - 1] with in [optLo, best].
  3. Recurse on the right half [mid + 1, hi] with in [best, optHi].

Each level of the recursion scans candidates in total, and there are levels, so one row costs and all rows .

def min_sum_squares_naive(a, k):
    n, INF = len(a), float("inf")
    pre = [0]
    for x in a:
        pre.append(pre[-1] + x)
    prev = [0] + [INF] * n                         # dp[0][*]
    for _ in range(k):
        cur = [INF] * (n + 1)
        for i in range(1, n + 1):
            for j in range(i):
                if prev[j] < INF:
                    cur[i] = min(cur[i], prev[j] + (pre[i] - pre[j]) ** 2)
        prev = cur
    return prev[n]


def min_sum_squares_dnc(a, k):
    n, INF = len(a), float("inf")
    pre = [0]
    for x in a:
        pre.append(pre[-1] + x)
    prev = [0] + [INF] * n

    def solve(cur, lo, hi, opt_lo, opt_hi):
        if lo > hi:
            return
        mid = (lo + hi) // 2
        best, best_j = INF, opt_lo
        for j in range(opt_lo, min(mid - 1, opt_hi) + 1):
            if prev[j] < INF:
                v = prev[j] + (pre[mid] - pre[j]) ** 2
                if v < best:
                    best, best_j = v, j
        cur[mid] = best
        solve(cur, lo, mid - 1, opt_lo, best_j)
        solve(cur, mid + 1, hi, best_j, opt_hi)

    for _ in range(k):
        cur = [INF] * (n + 1)
        solve(cur, 1, n, 0, n - 1)
        prev = cur
    return prev[n]


import random
assert min_sum_squares_naive([1, 2, 3, 4, 5, 6], 3) == 153 == min_sum_squares_dnc([1, 2, 3, 4, 5, 6], 3)
random.seed(11)
for _ in range(300):
    arr = [random.randint(0, 20) for _ in range(random.randint(1, 12))]
    kk = random.randint(1, len(arr))
    assert min_sum_squares_naive(arr, kk) == min_sum_squares_dnc(arr, kk)

Other tools for the same bottleneck, all covered in DP Optimizations:

  • Knuth's optimisation (when opt[g-1][i] <= opt[g][i] <= opt[g][i+1]): total.
  • Convex hull trick / Li Chao tree: when the cost expands into a product of a term in and a term in , as does, each row becomes or .
  • The "Aliens" trick (Lagrangian relaxation, also called WQS binary search): remove the "exactly groups" constraint by charging a penalty per group, solve the 1-D problem, and binary search on . Named after IOI 2016 problem "Aliens". Works when the optimum is convex in .

The ladder: brute force → better → optimal

Problem: split array largest sum, elements into groups.

Rung 1: try every set of cut points

Choose of the gaps: splits, each evaluated in .

from itertools import combinations


def split_brute(a, k):
    n, best = len(a), None
    for cuts in combinations(range(1, n), k - 1):
        bounds = (0,) + cuts + (n,)
        worst = max(sum(a[bounds[t]:bounds[t + 1]]) for t in range(k))
        best = worst if best is None else min(best, worst)
    return best


assert split_brute([7, 2, 5, 10, 8], 2) == 18

Rung 2: memoised recursion

f(g, i) = best for the first elements in groups. states, choices each: , with recursion.

Rung 3: tabulation

The same , iterative, with prefix sums and a cut table for reconstruction. Two rolling rows bring memory to .

Rung 4a: binary search on the answer (bottleneck objectives only)

. The usual interview answer for this problem.

Rung 4b: monotone-opt speed-ups (sum objectives)

Divide and conquer optimisation, ; or convex hull trick, ; or Aliens to remove the factor.

RungMethodTimeSpaceWhy it is better
1All cut setsBaseline / test oracle
2Memoised recursion + stackEach (groups, prefix) state once
3Tabulation, rollingNo recursion, reconstruction table
4aBinary search on answer extraDifferent idea: decide, don't optimise
4bD&C optimisation per rowUses monotone optimal cut points

Correctness

The partition recurrence. Every split of a[0..i-1] into non-empty contiguous groups has a last group a[j..i-1] for exactly one , and removing it leaves a split of a[0..j-1] into groups. Conversely, any split of the prefix plus the last group is a valid split. So the set of all splits is partitioned by . Within one , the total is combine(value of the prefix split, cost(j, i)), and combine is monotone in its first argument (+ and max both are): a better prefix split never makes the total worse. Therefore the best total for that uses the best prefix split, dp[g-1][j], and minimising over is exact. Induction on (all dp[g-1][j] with are filled first) completes the proof.

The monotonicity of combine is the condition to check for new problems. "Sum of averages" (+) and "largest group" (max) pass. An objective like "the second largest group sum" would not decompose this way.

Greedy feasibility for split array. Claim: if any split into groups with all sums exists, the greedy (extend the current group while it fits) uses groups. Proof by "staying ahead": let the greedy's groups end at and some valid split's groups end at . By induction : for , the greedy extends as far as possible, so ; if , then the elements from to are a sub-range of the valid group , whose sum is (non-negative values), so the greedy can reach at least . Hence the greedy finishes no later than the valid split, with no more groups. (This argument needs non-negative values.)

Monotone predicate. If cap is feasible, so is (the same split works). So binary search finds the smallest feasible cap, which equals the optimum of the DP.

Word wrap. The cost of a layout is a sum of independent per-line costs, and a layout is a path from word 0 to the end in the DAG of possible lines; the DP computes the shortest path in reverse topological order. Each line's cost depends only on its own words and whether it is last, which is why the "last line free" rule fits without extra state.

D&C optimisation. Correct whenever opt[g][i] is non-decreasing in (for some choice of argmin, e.g. the smallest). Proving that for a specific cost goes through the quadrangle inequality (Yao 1980; see cp-algorithms for the standard argument). In practice, verify by comparing with the naive DP on random inputs, as this lesson's code does.

Complexity

ProblemTimeSpaceNotes
Fixed , generic cost, rollingwith cost via prefix sums
Unlimited groupsword wrap, palindrome partitioning
Word wrap with max line length wordsthe inner loop stops when the line overflows
Split array, binary search = sum;
D&C optimisationneeds monotone opt
Convex hull trickneeds a linear-in- decomposition
Aliens trick + CHTneeds convexity in

Real numbers: LeetCode 410 has and , so the DP is , fine in C++, slow in Python; the binary search is about steps. CSES "Array Division" has : only the binary search fits.

Implementation

Two programs in four languages. The first solves split array largest sum both ways (DP with the cut points, and binary search on the answer) and checks them against each other. The second is word wrap with the chosen line breaks.

from itertools import combinations
import random


def split_array_dp(a, k):
    """Return (min possible largest group sum, list of groups) for exactly k contiguous groups."""
    n = len(a)
    pre = [0]
    for x in a:
        pre.append(pre[-1] + x)
    INF = float("inf")
    dp = [[INF] * (n + 1) for _ in range(k + 1)]
    cut = [[0] * (n + 1) for _ in range(k + 1)]
    dp[0][0] = 0
    for g in range(1, k + 1):
        for i in range(g, n + 1):
            for j in range(g - 1, i):                 # last group is a[j..i-1]
                v = max(dp[g - 1][j], pre[i] - pre[j])
                if v < dp[g][i]:
                    dp[g][i], cut[g][i] = v, j
    groups, i = [], n
    for g in range(k, 0, -1):                          # walk the cut points back
        j = cut[g][i]
        groups.append(a[j:i])
        i = j
    return dp[k][n], groups[::-1]


def feasible(a, cap, k):
    groups, cur = 1, 0
    for x in a:
        if x > cap:
            return False
        if cur + x > cap:                              # close the group, start a new one
            groups, cur = groups + 1, x
        else:
            cur += x
    return groups <= k


def split_array_binary_search(a, k):
    lo, hi = max(a), sum(a)
    while lo < hi:                                     # first cap that is feasible
        mid = (lo + hi) // 2
        if feasible(a, mid, k):
            hi = mid
        else:
            lo = mid + 1
    return lo


def brute(a, k):
    n, best = len(a), None
    for cuts in combinations(range(1, n), k - 1):
        b = (0,) + cuts + (n,)
        worst = max(sum(a[b[t]:b[t + 1]]) for t in range(k))
        best = worst if best is None else min(best, worst)
    return best


if __name__ == "__main__":
    assert split_array_dp([7, 2, 5, 10, 8], 2) == (18, [[7, 2, 5], [10, 8]])
    assert split_array_dp([7, 2, 5, 10, 8], 3)[0] == 14
    assert split_array_dp([1, 4, 4], 3) == (4, [[1], [4], [4]])
    assert split_array_binary_search([7, 2, 5, 10, 8], 2) == 18
    assert split_array_binary_search([1, 2, 3, 4, 5], 2) == 9
    assert split_array_binary_search([10], 1) == 10
    random.seed(2)
    for _ in range(300):
        a = [random.randint(0, 15) for _ in range(random.randint(1, 9))]
        k = random.randint(1, len(a))
        d, groups = split_array_dp(a, k)
        assert d == split_array_binary_search(a, k) == brute(a, k)
        assert len(groups) == k and all(groups) and sum(groups, []) == a
        assert max(sum(g) for g in groups) == d
    print("split array tests passed")
import java.util.ArrayList;
import java.util.List;

public class SplitArray {
    /** Exactly k contiguous groups; returns the min largest sum and fills groups with the split. */
    static long splitArrayDp(int[] a, int k, List<List<Integer>> groups) {
        int n = a.length;
        long[] pre = new long[n + 1];
        for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
        long INF = Long.MAX_VALUE;
        long[][] dp = new long[k + 1][n + 1];
        int[][] cut = new int[k + 1][n + 1];
        for (long[] row : dp) java.util.Arrays.fill(row, INF);
        dp[0][0] = 0;
        for (int g = 1; g <= k; g++)
            for (int i = g; i <= n; i++)
                for (int j = g - 1; j < i; j++) {
                    if (dp[g - 1][j] == INF) continue;
                    long v = Math.max(dp[g - 1][j], pre[i] - pre[j]);
                    if (v < dp[g][i]) {
                        dp[g][i] = v;
                        cut[g][i] = j;
                    }
                }
        groups.clear();
        int i = n;
        for (int g = k; g >= 1; g--) {
            int j = cut[g][i];
            List<Integer> grp = new ArrayList<>();
            for (int t = j; t < i; t++) grp.add(a[t]);
            groups.add(0, grp);
            i = j;
        }
        return dp[k][n];
    }

    static boolean feasible(int[] a, long cap, int k) {
        int groups = 1;
        long cur = 0;
        for (int x : a) {
            if (x > cap) return false;
            if (cur + x > cap) { groups++; cur = x; }
            else cur += x;
        }
        return groups <= k;
    }

    static long splitArrayBinarySearch(int[] a, int k) {
        long lo = 0, hi = 0;
        for (int x : a) { lo = Math.max(lo, x); hi += x; }
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (feasible(a, mid, k)) hi = mid; else lo = mid + 1;
        }
        return lo;
    }

    public static void main(String[] args) {
        List<List<Integer>> groups = new ArrayList<>();
        check(splitArrayDp(new int[]{7, 2, 5, 10, 8}, 2, groups) == 18);
        check(groups.equals(List.of(List.of(7, 2, 5), List.of(10, 8))));
        check(splitArrayDp(new int[]{7, 2, 5, 10, 8}, 3, groups) == 14);
        check(splitArrayDp(new int[]{1, 4, 4}, 3, groups) == 4);
        check(splitArrayBinarySearch(new int[]{7, 2, 5, 10, 8}, 2) == 18);
        check(splitArrayBinarySearch(new int[]{1, 2, 3, 4, 5}, 2) == 9);
        check(splitArrayBinarySearch(new int[]{10}, 1) == 10);
        java.util.Random rnd = new java.util.Random(2);
        for (int t = 0; t < 500; t++) {
            int n = 1 + rnd.nextInt(9);
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = rnd.nextInt(16);
            int k = 1 + rnd.nextInt(n);
            check(splitArrayDp(a, k, groups) == splitArrayBinarySearch(a, k));
        }
        System.out.println("split array tests passed");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError("test failed");
    }
}
#include <algorithm>
#include <cassert>
#include <climits>
#include <iostream>
#include <random>
#include <vector>
using namespace std;

long long splitArrayDp(const vector<int>& a, int k, vector<vector<int>>& groups) {
    int n = a.size();
    vector<long long> pre(n + 1, 0);
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
    const long long INF = LLONG_MAX;
    vector<vector<long long>> dp(k + 1, vector<long long>(n + 1, INF));
    vector<vector<int>> cut(k + 1, vector<int>(n + 1, 0));
    dp[0][0] = 0;
    for (int g = 1; g <= k; g++)
        for (int i = g; i <= n; i++)
            for (int j = g - 1; j < i; j++) {
                if (dp[g - 1][j] == INF) continue;
                long long v = max(dp[g - 1][j], pre[i] - pre[j]);
                if (v < dp[g][i]) { dp[g][i] = v; cut[g][i] = j; }
            }
    groups.assign(k, {});
    for (int g = k, i = n; g >= 1; g--) {
        int j = cut[g][i];
        groups[g - 1] = vector<int>(a.begin() + j, a.begin() + i);
        i = j;
    }
    return dp[k][n];
}

bool feasible(const vector<int>& a, long long cap, int k) {
    int groups = 1;
    long long cur = 0;
    for (int x : a) {
        if (x > cap) return false;
        if (cur + x > cap) { groups++; cur = x; }
        else cur += x;
    }
    return groups <= k;
}

long long splitArrayBinarySearch(const vector<int>& a, int k) {
    long long lo = *max_element(a.begin(), a.end()), hi = 0;
    for (int x : a) hi += x;
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (feasible(a, mid, k)) hi = mid; else lo = mid + 1;
    }
    return lo;
}

int main() {
    vector<vector<int>> groups;
    assert(splitArrayDp({7, 2, 5, 10, 8}, 2, groups) == 18);
    assert((groups == vector<vector<int>>{{7, 2, 5}, {10, 8}}));
    assert(splitArrayDp({7, 2, 5, 10, 8}, 3, groups) == 14);
    assert(splitArrayDp({1, 4, 4}, 3, groups) == 4);
    assert(splitArrayBinarySearch({7, 2, 5, 10, 8}, 2) == 18);
    assert(splitArrayBinarySearch({1, 2, 3, 4, 5}, 2) == 9);
    assert(splitArrayBinarySearch({10}, 1) == 10);
    mt19937 rng(2);
    for (int t = 0; t < 500; t++) {
        int n = 1 + rng() % 9;
        vector<int> a(n);
        for (int& x : a) x = rng() % 16;
        int k = 1 + rng() % n;
        assert(splitArrayDp(a, k, groups) == splitArrayBinarySearch(a, k));
    }
    cout << "split array tests passed\n";
    return 0;
}
function splitArrayDp(a: number[], k: number): [number, number[][]] {
  const n = a.length;
  const pre = [0];
  for (const x of a) pre.push(pre[pre.length - 1] + x);
  const dp: number[][] = Array.from({ length: k + 1 }, () => new Array<number>(n + 1).fill(Infinity));
  const cut: number[][] = Array.from({ length: k + 1 }, () => new Array<number>(n + 1).fill(0));
  dp[0][0] = 0;
  for (let g = 1; g <= k; g++)
    for (let i = g; i <= n; i++)
      for (let j = g - 1; j < i; j++) {
        const v = Math.max(dp[g - 1][j], pre[i] - pre[j]);
        if (v < dp[g][i]) {
          dp[g][i] = v;
          cut[g][i] = j;
        }
      }
  const groups: number[][] = [];
  for (let g = k, i = n; g >= 1; g--) {
    const j = cut[g][i];
    groups.unshift(a.slice(j, i));
    i = j;
  }
  return [dp[k][n], groups];
}

function feasible(a: number[], cap: number, k: number): boolean {
  let groups = 1, cur = 0;
  for (const x of a) {
    if (x > cap) return false;
    if (cur + x > cap) {
      groups++;
      cur = x;
    } else cur += x;
  }
  return groups <= k;
}

function splitArrayBinarySearch(a: number[], k: number): number {
  let lo = Math.max(...a), hi = a.reduce((s, x) => s + x, 0);
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (feasible(a, mid, k)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

function assert(ok: boolean, msg = "test failed"): void {
  if (!ok) throw new Error(msg);
}

const eq = (x: unknown, y: unknown): boolean => JSON.stringify(x) === JSON.stringify(y);
assert(eq(splitArrayDp([7, 2, 5, 10, 8], 2), [18, [[7, 2, 5], [10, 8]]]));
assert(splitArrayDp([7, 2, 5, 10, 8], 3)[0] === 14);
assert(eq(splitArrayDp([1, 4, 4], 3), [4, [[1], [4], [4]]]));
assert(splitArrayBinarySearch([7, 2, 5, 10, 8], 2) === 18);
assert(splitArrayBinarySearch([1, 2, 3, 4, 5], 2) === 9);
assert(splitArrayBinarySearch([10], 1) === 10);
for (let t = 0; t < 500; t++) {
  const n = 1 + Math.floor(Math.random() * 9);
  const a = Array.from({ length: n }, () => Math.floor(Math.random() * 16));
  const k = 1 + Math.floor(Math.random() * n);
  assert(splitArrayDp(a, k)[0] === splitArrayBinarySearch(a, k));
}
console.log("split array tests passed");

Sums can exceed 32 bits ( values of ), hence long / long long. The Infinity checks in Java and C++ skip impossible prefix states so max(INF, …) never pretends to be a real answer.

Word wrap with the chosen line breaks

from typing import List, Tuple


def word_wrap(words: List[str], width: int) -> Tuple[int, List[str]]:
    """Minimise the sum of squared trailing spaces on every line except the last."""
    n = len(words)
    if any(len(w) > width for w in words):
        raise ValueError("a word is longer than the line")
    INF = float("inf")
    dp = [INF] * (n + 1)          # dp[i]: best cost for words[i:], with words[i] starting a line
    nxt = [n] * (n + 1)           # nxt[i]: the line starting at i ends before word nxt[i]
    dp[n] = 0
    for i in range(n - 1, -1, -1):
        line = -1                 # width of words[i..j] with single spaces
        for j in range(i, n):
            line += len(words[j]) + 1
            if line > width:
                break             # longer lines only get wider
            cost = 0 if j == n - 1 else (width - line) ** 2
            if cost + dp[j + 1] < dp[i]:
                dp[i], nxt[i] = cost + dp[j + 1], j + 1
    lines, i = [], 0
    while i < n:
        lines.append(" ".join(words[i:nxt[i]]))
        i = nxt[i]
    return dp[0], lines


def greedy_wrap(words: List[str], width: int) -> List[str]:
    lines, cur = [], ""
    for w in words:
        if cur and len(cur) + 1 + len(w) > width:
            lines.append(cur)
            cur = w
        else:
            cur = w if not cur else cur + " " + w
    if cur:
        lines.append(cur)
    return lines


def raggedness(lines: List[str], width: int) -> int:
    return sum((width - len(l)) ** 2 for l in lines[:-1])


if __name__ == "__main__":
    words = "aaa bb cc ddddd".split()
    assert word_wrap(words, 6) == (10, ["aaa", "bb cc", "ddddd"])
    assert greedy_wrap(words, 6) == ["aaa bb", "cc", "ddddd"]
    assert raggedness(greedy_wrap(words, 6), 6) == 16
    text = "the quick brown fox jumps over the lazy dog".split()
    cost, lines = word_wrap(text, 10)
    assert cost == raggedness(lines, 10)
    assert cost <= raggedness(greedy_wrap(text, 10), 10)
    assert all(len(l) <= 10 for l in lines) and " ".join(lines).split() == text
    assert word_wrap([], 5) == (0, [])
    assert word_wrap(["hello"], 5) == (0, ["hello"])
    print("word wrap tests passed")
import java.util.ArrayList;
import java.util.List;

public class WordWrap {
    /** Returns the minimum cost and fills lines with the chosen layout. */
    static long wordWrap(String[] words, int width, List<String> lines) {
        int n = words.length;
        long INF = Long.MAX_VALUE;
        long[] dp = new long[n + 1];
        int[] nxt = new int[n + 1];
        java.util.Arrays.fill(dp, INF);
        dp[n] = 0;
        for (int i = n - 1; i >= 0; i--) {
            int line = -1;
            for (int j = i; j < n; j++) {
                line += words[j].length() + 1;
                if (line > width) break;
                long cost = j == n - 1 ? 0 : (long) (width - line) * (width - line);
                if (dp[j + 1] != INF && cost + dp[j + 1] < dp[i]) {
                    dp[i] = cost + dp[j + 1];
                    nxt[i] = j + 1;
                }
            }
        }
        lines.clear();
        for (int i = 0; i < n; i = nxt[i])
            lines.add(String.join(" ", java.util.Arrays.copyOfRange(words, i, nxt[i])));
        return dp[0];
    }

    public static void main(String[] args) {
        List<String> lines = new ArrayList<>();
        check(wordWrap("aaa bb cc ddddd".split(" "), 6, lines) == 10);
        check(lines.equals(List.of("aaa", "bb cc", "ddddd")));
        String[] text = "the quick brown fox jumps over the lazy dog".split(" ");
        long cost = wordWrap(text, 10, lines);
        long check = 0;
        for (int i = 0; i + 1 < lines.size(); i++) check += (long) (10 - lines.get(i).length()) * (10 - lines.get(i).length());
        check(cost == check);
        check(String.join(" ", lines).equals(String.join(" ", text)));
        check(wordWrap(new String[]{"hello"}, 5, lines) == 0 && lines.equals(List.of("hello")));
        System.out.println("word wrap tests passed");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError("test failed");
    }
}
#include <cassert>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

long long wordWrap(const vector<string>& words, int width, vector<string>& lines) {
    int n = words.size();
    const long long INF = LLONG_MAX;
    vector<long long> dp(n + 1, INF);
    vector<int> nxt(n + 1, n);
    dp[n] = 0;
    for (int i = n - 1; i >= 0; i--) {
        int line = -1;
        for (int j = i; j < n; j++) {
            line += (int)words[j].size() + 1;
            if (line > width) break;
            long long cost = j == n - 1 ? 0 : 1LL * (width - line) * (width - line);
            if (dp[j + 1] != INF && cost + dp[j + 1] < dp[i]) { dp[i] = cost + dp[j + 1]; nxt[i] = j + 1; }
        }
    }
    lines.clear();
    for (int i = 0; i < n; i = nxt[i]) {
        string s;
        for (int t = i; t < nxt[i]; t++) s += (t > i ? " " : "") + words[t];
        lines.push_back(s);
    }
    return dp[0];
}

int main() {
    vector<string> lines;
    assert(wordWrap({"aaa", "bb", "cc", "ddddd"}, 6, lines) == 10);
    assert((lines == vector<string>{"aaa", "bb cc", "ddddd"}));
    vector<string> text = {"the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"};
    long long cost = wordWrap(text, 10, lines), check = 0;
    for (size_t i = 0; i + 1 < lines.size(); i++) check += 1LL * (10 - (int)lines[i].size()) * (10 - (int)lines[i].size());
    assert(cost == check);
    assert(wordWrap({"hello"}, 5, lines) == 0 && lines.size() == 1);
    cout << "word wrap tests passed\n";
    return 0;
}
function wordWrap(words: string[], width: number): [number, string[]] {
  const n = words.length;
  const dp = new Array<number>(n + 1).fill(Infinity);
  const nxt = new Array<number>(n + 1).fill(n);
  dp[n] = 0;
  for (let i = n - 1; i >= 0; i--) {
    let line = -1;
    for (let j = i; j < n; j++) {
      line += words[j].length + 1;
      if (line > width) break;
      const cost = j === n - 1 ? 0 : (width - line) ** 2;
      if (cost + dp[j + 1] < dp[i]) {
        dp[i] = cost + dp[j + 1];
        nxt[i] = j + 1;
      }
    }
  }
  const lines: string[] = [];
  for (let i = 0; i < n; i = nxt[i]) lines.push(words.slice(i, nxt[i]).join(" "));
  return [dp[0], lines];
}

function assert(ok: boolean, msg = "test failed"): void {
  if (!ok) throw new Error(msg);
}

const eq = (x: unknown, y: unknown): boolean => JSON.stringify(x) === JSON.stringify(y);
assert(eq(wordWrap(["aaa", "bb", "cc", "ddddd"], 6), [10, ["aaa", "bb cc", "ddddd"]]));
const text = "the quick brown fox jumps over the lazy dog".split(" ");
const [cost, lines] = wordWrap(text, 10);
const check = lines.slice(0, -1).reduce((s, l) => s + (10 - l.length) ** 2, 0);
assert(cost === check && lines.join(" ") === text.join(" "));
assert(eq(wordWrap(["hello"], 5), [0, ["hello"]]));
console.log("word wrap tests passed");

The inner loop breaks as soon as the line overflows, so the real cost is where is the most words that fit on one line, usually a small constant: word wrap is effectively linear.

Real-world uses

  • Typesetting. TeX and LaTeX break every paragraph with the Knuth–Plass DP (1981), and the same algorithm or close relatives appear in other typesetting systems (Adobe InDesign's paragraph composer is commonly described as Knuth–Plass-inspired, though its exact algorithm is proprietary). Simple editors and terminals use the greedy instead, because it is streaming and good enough for monospaced text.
  • Histograms for query optimisers. A database estimates how many rows a filter like price BETWEEN 10 AND 20 returns from a histogram of the column. The V-optimal histogram picks bucket boundaries over sorted values to minimise the total squared error, which is exactly the sum-of-squares partition DP in (Jagadish, Koudas, Muthukrishnan, Poosala, Sevcik and Suel, VLDB 1998). Production systems often use cheaper equi-depth histograms because of that cost.
  • 1-D clustering and map classification. Optimal -means on one dimension is partition DP over sorted values (Wang and Song, The R Journal 2011, the Ckmeans.1d.dp package; later sped up with divide-and-conquer and SMAWK-style tricks). Jenks "natural breaks", a standard classification for choropleth maps in GIS tools such as ArcGIS and QGIS, solves the same problem.
  • Sharding and load balancing over ordered keys. Range-partitioned stores (Bigtable/HBase regions, CockroachDB ranges) want contiguous key ranges with balanced load. Choosing split points to minimise the hottest shard is split array largest sum; systems usually do it incrementally (split hot ranges) rather than globally, but offline rebalancers and batch schedulers use the binary-search version. See Sharding for the system side.
  • Parallel work splitting. Giving threads contiguous chunks of an array of tasks with different costs, so the slowest thread finishes soonest, is the painter's partition.
  • Time-series and genome segmentation. Fitting piecewise-constant or piecewise-linear models (change-point detection) is Bellman's 1961 segmentation DP; the PELT algorithm (Killick, Fearnhead and Eckley, 2012) prunes it to near-linear time for the "penalty per segment" version.

Pitfalls & edge cases

  • Empty groups. "Split into non-empty groups" needs in the loop and . Allowing creates empty groups and can produce wrong answers (an empty group has sum 0, which looks great for a max).
  • . Impossible with non-empty groups. Decide what to return; LeetCode guarantees .
  • Binary search bounds. lo = max(a), not 0 or 1: with lo = 0 the greedy may loop on a single element larger than the cap (or you must handle x > cap explicitly, as this lesson's code does).
  • Negative numbers break the greedy feasibility check. Use the DP, or a different feasibility argument.
  • Off-by-one in the last-line rule. Word wrap's last line is free; forgetting this makes the DP cram text at the end. Also check whether the problem counts trailing spaces, cubes them, or charges the last line.
  • A word longer than the line. No valid layout; return an error or allow overflow with a huge penalty.
  • Recomputing group sums in the inner loop. That adds a factor of . Prefix sums.
  • Float averages. LeetCode 813 compares with tolerance ; summing fractions in a different order can differ in the last bits, so do not test floats with == (this lesson's code uses a tolerance).
  • Reconstruction with rolling rows. Two-row DP loses the cut table; keep the full cut (it is ints) or recompute.
  • Applying D&C optimisation without monotone opt. It silently returns wrong answers. Always validate against the naive DP on random tests.

Variations

  • Partition array for maximum sum (LeetCode 1043): each group has length at most and is replaced by its maximum; unlimited groups, dp[i] = max over last length t <= L of dp[i-t] + t * max(a[i-t..i-1]).
  • Minimum difficulty of a job schedule (LeetCode 1335): exactly days, each day's difficulty is the max job that day: fixed- template with cost = max.
  • Filling bookcase shelves (LeetCode 1105): unlimited groups, each shelf's width ≤ W, cost = tallest book on the shelf.
  • Allocate mailboxes (LeetCode 1478): groups of sorted houses, each group served by a mailbox at its median; cost precomputed in .
  • Ship within D days (LeetCode 1011): the binary-search twin of split array largest sum.
  • Minimum cost to split an array (LeetCode 2547): unlimited groups, cost = a constant plus the number of elements that repeat inside the group; compute group costs incrementally while extending leftwards.
  • Count partitions instead of optimising: "number of ways to split into valid pieces" uses the same dp[i] = sum dp[j] (word combinations, decode ways).
  • Interval table + partition DP: Palindrome Partitioning III, allocate mailboxes, "minimum cost to make every block X". Precompute cost(j, i) with an interval DP or prefix trick, then partition.
  • Line breaking with hyphenation and stretch: Knuth–Plass; with a maximum number of lines, add a group dimension.

Practice ladder

Each problem is described in my own words; follow the link for the full statement.

1. Partition Array for Maximum Sum (LeetCode 1043) — Cut into pieces of length at most ; each piece becomes copies of its maximum; maximise the total. Teaches the unlimited-groups template with a running max.

Solution
def max_sum_after_partitioning(a, L):
    n = len(a)
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        mx = 0
        for t in range(1, min(L, i) + 1):         # last piece is a[i-t..i-1]
            mx = max(mx, a[i - t])
            dp[i] = max(dp[i], dp[i - t] + mx * t)
    return dp[n]


assert max_sum_after_partitioning([1, 15, 7, 9, 2, 5, 10], 3) == 84
assert max_sum_after_partitioning([1, 4, 1, 5, 7, 3, 6, 1, 9, 9, 3], 4) == 83

Extending the last piece leftwards keeps the running max in .

2. Capacity To Ship Packages Within D Days (LeetCode 1011) — Smallest ship capacity that moves all packages, in order, within days. Teaches binary search on the answer with the greedy check.

Hint

split_array_binary_search(weights, D) from this lesson is a full solution.

3. Split Array Largest Sum (LeetCode 410) — The lesson's main problem. Teaches both approaches.

Solution

Either function above. In an interview, start with the DP (shows you know the template), then offer binary search as the optimisation.

4. Array Division (CSES 1085) — The same problem with . Teaches that only the method fits.

Hint

64-bit sums. The DP would need about steps; binary search needs about .

5. Palindrome Partitioning II (LeetCode 132) — Fewest cuts into palindromes. Teaches interval precomputation feeding a 1-D partition DP.

Hint

Covered in full in String DP.

6. Minimum Difficulty of a Job Schedule (LeetCode 1335) — Jobs in order over exactly days, at least one per day; a day's difficulty is its hardest job; minimise the sum. Teaches fixed- with a max cost.

Solution
def min_difficulty(jobs, d):
    n = len(jobs)
    if n < d:
        return -1
    INF = float("inf")
    prev = [0] + [INF] * n                         # 0 days: only the empty prefix
    for g in range(1, d + 1):
        cur = [INF] * (n + 1)
        for i in range(g, n + 1):
            mx = 0
            for j in range(i - 1, g - 2, -1):      # last day does jobs j..i-1
                mx = max(mx, jobs[j])
                cur[i] = min(cur[i], prev[j] + mx)
        prev = cur
    return prev[n]


assert min_difficulty([6, 5, 4, 3, 2, 1], 2) == 7
assert min_difficulty([9, 9, 9], 4) == -1
assert min_difficulty([1, 1, 1], 3) == 3

7. Largest Sum of Averages (LeetCode 813) — Maximise the sum of group averages with at most groups. Teaches the max version.

Hint

largest_sum_of_averages in section 6.

8. Filling Bookcase Shelves (LeetCode 1105) — Books in order onto shelves of width ; each shelf is as tall as its tallest book; minimise total height. Teaches unlimited groups with two running quantities (width and max height).

Hint

dp[i] = min over the start j of the last shelf (while width fits) of dp[j] + max height of books j..i-1.

9. Check if There is a Valid Partition For The Array (LeetCode 2369) — Can the array be cut into blocks of 2 equal, 3 equal, or 3 consecutive increasing values? Teaches a boolean partition DP with tiny group lengths.

Hint

ok[i] = (ok[i-2] and block of 2 valid) or (ok[i-3] and block of 3 valid).

10. Allocate Mailboxes (LeetCode 1478) — Place mailboxes on a street to minimise total walking distance from houses. Teaches "sort, then precompute group cost (median) + partition".

Hint

Sorted houses; cost(j, i) = sum of distances to the median of houses , computable from cost(j+1, i-1) plus the two ends. Then dp[g][i].

11. Palindrome Partitioning III (LeetCode 1278) — Fewest letter changes so the string splits into exactly palindromes. Teaches interval cost table + fixed- partition.

Hint

See section 3 above and the String DP lesson.

12. Minimum Cost to Split an Array (LeetCode 2547) — Each piece costs a constant plus the number of its elements that appear more than once in it. Teaches incremental group cost while extending leftwards.

Hint

For a fixed end , move leftwards, keeping counts; "trimmed length" increases by 2 when a value's count goes from 1 to 2, by 1 after that.

13. Ciel and Gondolas (Codeforces 321E) — Split a queue of people into consecutive gondolas, minimising total unfamiliarity within gondolas. Teaches divide-and-conquer optimisation for real.

Hint

2-D prefix sums give cost(j, i) in . Naive is too slow; D&C optimisation is . Fast input matters.

Common mistakes & interview follow-ups

"Why not just binary search?" It is the better answer for split array largest sum. Explain the monotone predicate and the greedy check, and that it only works for bottleneck objectives with non-negative values.

"What if the numbers can be negative?" The greedy check fails (a later negative number could make an over-full group fine). Use the DP.

"Return the actual split." Store the best per cell (or re-run the greedy at the optimal cap) and walk back.

"The greedy text wrap is what editors do. Why DP?" Show aaa bb cc ddddd with width 6: greedy 16, DP 10. Mention Knuth–Plass in TeX.

"Make the DP faster." Name divide-and-conquer optimisation and the monotone-opt condition; mention the convex hull trick for squared costs and the Aliens trick for removing .

"Groups don't need to be contiguous." Then it is a different, generally NP-hard problem (multiway number partitioning); small uses bitmask DP.

Mistakes interviewers watch for: allowing empty groups; wrong binary-search bounds; recomputing sums in the inner loop; charging the last line in word wrap; float equality in averages.

Quick quiz

1. For [7, 2, 5, 10, 8] with , which wins in dp[2][5] and why?

Answer

: the split [7, 2, 5] | [10, 8] has group sums 14 and 18, so its max is 18; every other gives a larger max (25, 23, 24).

2. Why must binary search start at lo = max(a) rather than 0?

Answer

No group can have a sum below the largest element, so any cap smaller than max(a) is infeasible; starting there also keeps the greedy from facing an element it can never place.

3. In word wrap, why square the slack instead of adding it?

Answer

Every layout with the same number of lines has the same total slack, so plain sums cannot distinguish an even paragraph from a ragged one. Squaring punishes one big gap more than several small gaps.

4. Which problems in this lesson can use binary search on the answer, and which cannot?

Answer

Split array largest sum / painter's partition / ship within D days (bottleneck objectives with a greedy check) can. Sum of squares, word wrap, max average and palindrome partitioning cannot; they need the DP.

5. What condition makes divide-and-conquer optimisation valid?

Answer

The best start of the last group, opt[g][i], must be non-decreasing in . It follows from the quadrangle inequality on the group cost.

Further reading / sources

  • Steven S. Skiena, The Algorithm Design Manual (2nd ed. 2008 §8.5, 3rd ed. 2020), "The Partition Problem" (linear partition, the M[n][k] recurrence and reconstruction).
  • Donald E. Knuth and Michael F. Plass, "Breaking Paragraphs into Lines", Software: Practice and Experience 11(11), 1981.
  • Richard Bellman, "On the approximation of curves by line segments using dynamic programming", Communications of the ACM 4(6), 1961.
  • H. V. Jagadish et al., "Optimal Histograms with Quality Guarantees", VLDB 1998.
  • Haizhou Wang and Mingzhou Song, "Ckmeans.1d.dp: Optimal k-means Clustering in One Dimension by Dynamic Programming", The R Journal 3(2), 2011.
  • F. Frances Yao, "Efficient dynamic programming using quadrangle inequalities", STOC 1980.
  • cp-algorithms, Divide and Conquer DP and Knuth's Optimization.
  • Rebecca Killick, Paul Fearnhead and Idris Eckley, "Optimal detection of changepoints with a linear computational cost", JASA 107(500), 2012.

Lessons: previous — Interval DP · next — Tree DP · module — Dynamic Programming · course — DSA: Zero to Mastery.

Related Archon pages: Binary Search · Prefix Sums · String DP · Interval DP · Topological Sort · Sharding · DP Optimizations · Bitmask DP.