Algorithms Catch-Up · The Index Is an Amount, the Value Is a Count: Dynamic Programming and Backtracking

Deterministic Unigram encoding uses dynamic programming to save the best score for each prefix. Its final piece can jump directly from position 4 to position 6. The answer at position 5 has already been computed, but the final path does not use it.

Three questions deserve their own explanation: what exactly does a table cell mean, why can its answer be reused, and how do saved scores become a path? Set probabilities and strings aside for a moment. A table with seven cells is enough to work through all three.

Fix the problem: exact amount, fewest coins

The available coin values are 1, 3 and 4, with unlimited coins of each value. Make exactly 6, using as few coins as possible. Amounts below are in currency units; counts are in coins.

Taking the largest coin that fits the remaining amount gives 4 + 1 + 1. That greedy rule fails for these denominations. The largest coin now does not guarantee the best way to make the remainder.

Instead, find the minimum count for amounts 0, 1, 2, … and build the answer for 6 from those results. Dynamic programming here means saving answers to reusable subproblems and solving larger problems in dependency order.

Keep all three conditions: positive integer denominations, unlimited supply, and an exact target. They determine the calculation order, whether the state contains enough information, and which candidates are legal.

The index is an amount; the value is a count

Define:

dp[x] = the minimum number of coins needed to make exactly amount x

For example, dp[5] = 2 means making amount 5 needs at least two coins, such as 4 + 1. The 5 inside the brackets and the returned 2 have different units.

Locate by amount, then read a count. The 3 in dp[3] does not mean three coins. Here dp[3] = 1, because a single coin of value 3 is enough.

Why start at zero, with infinity elsewhere?

dp = [0, float("inf"), float("inf"), float("inf"),
      float("inf"), float("inf"), float("inf")]
choice = [None] * 7

dp[0] = 0 is a known answer: taking no coins makes exactly zero. It also supplies a starting point. To make amount 3 with a final coin of value 3, the recurrence reads dp[0].

Positive amounts begin at ∞, meaning no solution has been found yet. The first finite candidate can replace it. Starting them at zero would make every candidate larger than the stored value, so “update only when smaller” would never update anything.

Only after all candidates for an amount have been checked does a remaining ∞ mean unreachable. With a coin of value 1, every non-negative integer amount is reachable. With only 2 and 4, amount 3 remains at ∞.

★ Derive the recurrence by assuming a final coin

Suppose the final coin used to make amount x has value c. Remove it: the preceding coins must make exactly x − c.

Amount: (x − c) + c = x       currency + currency = currency
Count:  dp[x − c] + 1         coins + coins = coins

The +1 means one coin, not one currency unit. A final coin of value 4 still adds only one to the count.

Try every legal final denomination and take the smallest count:

dp[0] = 0

dp[x] = min { dp[x − c] + 1 | c ∈ {1, 3, 4}, c ≤ x }

If there is no feasible candidate, the minimum is ∞. Skip denominations larger than x. An unreachable remainder cannot be extended into a feasible solution either.

Why keep only the best preceding solution?

Suppose an optimal solution for x ends in coin c, and its preceding part uses m coins.

If that part is not optimal for x − c, there is a replacement using m′ < m coins. Replace the preceding part and append the same final coin:

Original:    m  + 1 coins, still making x
Replacement: m′ + 1 coins, still making x

m′ < m  ⇒  m′ + 1 < m + 1

That contradicts the original solution being optimal. Therefore once the final coin is fixed, the preceding solution must also be optimal. This is the problem’s optimal substructure. It follows from that replacement argument.

Now put both directions together:

1. Every complete solution has a final coin from the legal denominations. No possible ending is omitted.
2. For each fixed final coin, the best solution for the remainder plus that coin is a real, feasible solution.
3. The minimum of these candidates is therefore the minimum over all complete solutions.

Every possible final step is covered without enumerating every complete path. The part already solved can be reused.

Why is the amount enough to describe a state?

Two paths make amount 4: [4] and [1, 3]. Both can subsequently add exactly the same coins: an unlimited supply of 1, 3 and 4. Once two paths reach the same amount, the one using an extra coin cannot catch up later. Keeping only the minimum count is sufficient.

This relies on unlimited supply. If each coin may be used only once, the path taken affects what remains available. This recurrence and these loops cannot be copied unchanged. The reasoning must account for which coins are allowed so far. Such problems can also use a compressed one-dimensional array, but require a different iteration order; this implementation does not transfer directly.

Why increasing amounts never read an unfinished answer

Every denomination is positive, so:

x − c < x

Computing x = 1 → 2 → … → 6 means every legal dependency lies to the left and is already complete. This gives an induction proof: dp[0] is correct; if all smaller amounts are correct, the recurrence just derived correctly solves the current amount. The entire table is therefore correct when computed in that order.

One round solves one amount. There are six outer rounds. Within each, check final coins in the order c = 1, 3, 4. During the round, dp[x] is the best candidate checked so far. It becomes the final answer for that amount only after every denomination has been checked.

Every candidate in the table is a coin count. Denominations determine which cell to read.

A tie does not end the round

Round four first finds 2 and 2: a provisional tie. The third candidate is dp[0] + 1 = 1, which is better still. Equality decides that this candidate need not replace the record. It does not establish that the round’s final optimum has been found.

Round five finds 2, 3, 2, with two genuinely optimal ordered paths: 4 + 1 and 1 + 4. This implementation updates only on a strict improvement, so it retains the first path, 4 + 1, and choice[5] = 1. Trying denominations in the order 4, 3, 1 would record a final coin of 4 instead. The minimum count would still be 2.

choice records how to recover one optimal path. It neither claims uniqueness nor enumerates all tied solutions.

Slow down round six: where each candidate reads

At the start of this round, amounts 0–5 have final answers. Only dp[6] = ∞ is waiting for candidates.

Assume the last coin has value 1

Remainder: 6 − 1 = 5
Read:      dp[5] = 2 coins
Candidate: 2 + 1 = 3 coins       making 4 + 1 + 1 = 6
Compare:   3 < ∞
Update:    dp[6] = 3, choice[6] = 1

Three coins is best so far. Save it; two more final denominations remain to be tried.

Assume the last coin has value 3

Remainder: 6 − 3 = 3
Read:      dp[3] = 1 coin
Candidate: 1 + 1 = 2 coins       making 3 + 3 = 6
Compare:   2 < 3
Update:    dp[6] = 2, choice[6] = 3

The comparison happens before the write: compare candidate 2 with old value 3, then store 2. Looking at the updated table and comparing 2 with 2 would make it appear that equality caused an update.

Assume the last coin has value 4

Remainder: 6 − 4 = 2
Read:      dp[2] = 2 coins
Candidate: 2 + 1 = 3 coins       making 1 + 1 + 4 = 6
Compare:   3 > 2
Keep:      dp[6] = 2, choice[6] = 3

All three final denominations have now been checked. The answer for amount 6 is fixed at two coins.

Why not scan all the earlier cells?

Fixing x = 6 and c = 3 uniquely determines the preceding amount: 6 − 3 = 3. Read dp[3] directly. There is no second search from dp[0] through dp[5].

Extending the solution at dp[2] with a coin of value 3 would make 2 + 3 = 5. That is a candidate for round five. It does not satisfy round six’s requirement to make exactly 6.

A subproblem may certainly be smaller than the final target. The condition is: subproblem amount + final denomination = this round’s amount.

dp tells you how many; choice recovers which coins

The final tables are:

Amount x:   0     1  2  3  4  5  6
dp[x]:      0     1  2  1  1  2  2       coins
choice[x]:  None  1  1  3  4  1  3       currency units

dp[6] = 2 supplies only a count. To recover coins, start at the target amount and read choice:

This is amount minus denomination. Filling the table uses +1 to count coins; backtracking uses −c to find the remaining amount.

Why can choice always lead to the next step? When a record is written, it satisfies:

c = choice[x]
dp[x] = dp[x − c] + 1

Each recovered coin strictly decreases the remaining amount and decreases its required count by exactly one. For a reachable target, this eventually reaches dp[0] = 0, recovering exactly dp[target] coins.

Calculation order and the final path differ

Fill:      1 → 2 → 3 → 4 → 5 → 6     prepare every subproblem
Backtrace: 6 → 3 → 0                 recover only the chosen parts

Computing dp[5] does not force the final solution to pass through 5. It supplied the candidate ending in coin 1; that candidate lost the comparison.

Backtracking takes the last coin first, so it recovers a path in reverse order. Coin order does not affect the total amount. Reverse the result if a forward ordering is needed. For tokenization, order matters: the recovered token list must be reversed before output.

Walk through all six rounds and the backtrace

The animation contains all 50 steps: initialization, six rounds of selecting amounts and testing final coins, then backtracking. Reading, calculating and updating are shown separately. There are still only six outer iterations.

Click an amount in the memory table to jump to its round. Start with round six, then revisit round four’s provisional tie followed by an improvement. Each step includes the general rule, substituted values and the comparison result. Comparisons use the value before the write.

There are three distinct stopping conditions:

Translate the derivation directly into code

This implementation includes input validation, unreachable targets and backtracking. It needs no third-party packages. The input order of denominations determines which tied candidate is preferred.

def min_coins(coins, target):
    if type(target) is not int or target < 0:
        raise ValueError("target must be a non-negative integer")
    coins = tuple(coins)
    if any(type(c) is not int or c <= 0 for c in coins):
        raise ValueError("coin values must be positive integers")

    inf = float("inf")
    dp = [inf] * (target + 1)
    choice = [None] * (target + 1)
    dp[0] = 0

    for x in range(1, target + 1):
        for c in coins:
            if c > x:
                continue
            if dp[x - c] == inf:
                continue
            candidate = dp[x - c] + 1
            if candidate < dp[x]:
                dp[x] = candidate
                choice[x] = c

    if dp[target] == inf:
        return dp, choice, []

    picked = []
    remaining = target
    while remaining > 0:
        c = choice[remaining]
        picked.append(c)
        remaining -= c
    return dp, choice, picked

dp, choice, picked = min_coins([1, 3, 4], 6)
print(dp)       # [0, 1, 2, 1, 1, 2, 2]
print(choice)   # [None, 1, 1, 3, 4, 1, 3]
print(picked)   # [3, 3]

if c > x must precede the lookup. Python accepts negative indices: dp[-1] reads the end of the array. That is not a valid negative-amount subproblem, and Python will not automatically reject it for you.

An empty result does not distinguish zero from unreachable

Check dp[target] for reachability, rather than checking only whether the recovered list is empty.

Where the saved computation goes

dp[3] is read in round four when trying final coin 1, and again in round six when trying final coin 3. Both need the same subproblem. There is no reason to search for ways to make amount 3 twice. These are overlapping subproblems.

For target amount A and K denominations, the nested loops check at most A × K candidates, taking O(AK) time. The dp and choice arrays each contain A + 1 cells, requiring O(A) space. Backtracking takes one step per recovered coin. Because denominations are positive integers, the result contains at most A coins. This complexity is measured in the numerical amount A, not the number of bits needed to write it.

The animation additionally saves snapshots and complete paths for inspection. Those are not part of this solver’s space bound. The solver stores two arrays without copying a whole path for every amount.

What was checked numerically

An independent breadth-first search (BFS) expands by coin count: each edge adds one coin, so the first layer reaching an amount gives its minimum count. The denomination sets are [1,3,4], [2,4], [2,5], [1], [4,3,1] and []; targets run from 0 through 12, for 78 inputs.

Each case checks the entire dp table, the choice equality at every reachable state, and both the sum and count of recovered coins. All agree, including zero, unreachable targets, an empty denomination set and reordered ties. These finite tests check the implementation. The replacement argument and induction above establish the recurrence for all valid inputs.

Back to Unigram: different scores, the same final-step argument

An amount identifies a state in coin change. A prefix’s ending boundary identifies a state in deterministic Unigram encoding:

Assume nonempty pieces with positive probabilities. text[j:i] denotes the text from boundary j to boundary i. Consider every legal vocabulary piece ending exactly at i:

best[i] = max { best[j] + log p(text[j:i])
                | 0 ≤ j < i, text[j:i] is in the vocabulary }

For a fixed final piece, the added log p is the same. A worse prefix score remains worse after adding it, so retaining only the best score at that boundary is sufficient. Unigram piece probabilities do not depend on the preceding piece, which makes the prefix boundary a sufficient state here.

For abcabc, mark the boundaries:

0 a 1 b 2 c 3 a 4 b 5 c 6

With vocabulary a, b, c, ab, bc, abc, exactly three pieces can end at boundary 6:

A final bc must read boundary 4. Reading 5 and appending bc would not cover the text exactly. If bc wins, the final path takes 4 → 6 and can skip the already computed best[5]. That is the same structure as computing amount 5 but ultimately backtracking along 6 → 3 → 0.

Viterbi finds the highest-scoring path. Training expectations accumulate contributions from multiple segmentations, using sums or logsumexp in log space. A single best path cannot replace the weighted contributions of all paths. Section 3.2 of the original Unigram paper distinguishes the most probable segmentation from the marginal likelihood used for training.

When reading dp[...], turn it into a full sentence: which subproblem does this index define, what quantity does the cell store, and where does the final step extend it? Once the state has a precise meaning, the lookup, addition, comparison and backtrace all follow from it.