Counting, where the loop order changes the answer

The subtlest thing in either DP unit. Two nested loops, swapped, count two different things.

The two versions differ only in which loop is outer. Nothing else changes, and the answers are not close.

Here is the natural loop, which counts arrangements, with the same question listed out by hand underneath so the gap is visible.

1def count_arrangements(target, sizes):2    ways = [0] * (target + 1)3    ways[0] = 14    for amount in range(1, target + 1):        # amounts outside5        for size in sizes:6            if size <= amount:7                ways[amount] += ways[amount - size]8    return ways[target]9 10print("counted:", count_arrangements(4, [1, 2]))11print("listed: ", ["1+1+1+1", "1+1+2", "1+2+1", "2+1+1", "2+2"])12print("as multisets, ignoring order:", ["1+1+1+1", "1+1+2", "2+2"])

Five arrangements collapse to three combinations, because the three orderings of one 2 and two 1s are one multiset.

Key idea

This is a two-dimensional table collapsed

The combinations version is really a table indexed by which pieces are allowed and by the amount. The row for the first k pieces is built from the row for the first k minus 1.

Collapsing it to one array works because each row only reads the row above and cells to its left, which is why the pieces loop must be outermost. Seeing the collapsed version as a two-dimensional table is what makes the loop order obvious rather than arbitrary.

Below, nothing is computed. Each cell of one row is asked only where it reads from.

1target = 42size = 2                       # the piece this row is adding3 4for amount in range(target + 1):5    sources = ["the cell directly above (skip this piece)"]6    if size <= amount:7        sources.append(f"this row at {amount - size} (use it, and allow it again)")8    print(f"amount {amount} reads:", " + ".join(sources))

Only the row above and cells to the left, which is exactly what a single array can hold.

Quick check· 5 min

Which loop belongs on the outside?

Both versions have the same two loops, the same table, and the same update. Only the nesting differs. Which nesting counts each multiset once, so that 1 then 2 and 2 then 1 are not counted separately?

Pieces outside, amounts inside: finish the whole table for one piece before considering the nextAmounts outside, pieces inside: at each amount, try every pieceEither one; the nesting only affects speed, not the countNeither; counting multisets needs a second dimension that a single array cannot hold

Problem· 28 min

Coin Change Ii

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1def count_arrangements(target, sizes):2 ways = [0] * (target + 1)3 ways[0] = 14 for amount in range(1, target + 1): # amounts outside5 for size in sizes:6 if size <= amount:7 ways[amount] += ways[amount - size]8 return ways[target]9 10print("counted:", count_arrangements(4, [1, 2]))11print("listed: ", ["1+1+1+1", "1+1+2", "1+2+1", "2+1+1", "2+2"])12print("as multisets, ignoring order:", ["1+1+1+1", "1+1+2", "2+2"])

1target = 42size = 2 # the piece this row is adding3 4for amount in range(target + 1):5 sources = ["the cell directly above (skip this piece)"]6 if size <= amount:7 sources.append(f"this row at {amount - size} (use it, and allow it again)")8 print(f"amount {amount} reads:", " + ".join(sources))