Dynamic programming

Repeated subproblems

Dynamic programming stores answers to smaller problems so that repeated work is avoided. The difficult part is usually defining the state: exactly what one stored value means. Once that meaning is precise, derive a transition using smaller states, choose base cases, and evaluate states in a valid order.

A recurrence alone is not enough. If a recursive function recomputes the same states many times, it can still be exponential. Memoization stores results during recursion. Bottom-up computation fills a table in dependency order. Both can implement the same state definition.

A complete example

Count ways to reach a total using steps of size one or three. Let ways[s] mean the number of ordered step sequences whose sum is exactly s.

target = 5
ways = [0] * (target + 1)
ways[0] = 1

for total in range(1, target + 1):
    ways[total] += ways[total - 1]
    if total >= 3:
        ways[total] += ways[total - 3]

print(ways[target])

4

The sequences are five ones, then the three arrangements containing one three and two ones. The base case ways[0] = 1 counts the empty sequence. It allows a final step to build an exact total from a smaller one.

Every nonempty sequence ends in either one or three. Removing that last step gives one of the two smaller states. These cases are disjoint and include every valid sequence, so their counts can be added. The loop evaluates smaller totals first, making every dependency available.

There are target + 1 states and a constant number of transitions per state. Time and space are O(target). When only a small fixed window of earlier states is needed, space can sometimes be reduced, but first make the full table correct.

Counting order matters

The example counts ordered sequences. One followed by three and three followed by one are different. If a problem asks for an unordered collection instead, the state or loop order must prevent counting permutations multiple times. Copying a recurrence from a superficially similar problem can count the wrong objects.

Check the exact definition of the Fibonacci sequence in each statement. One exercise starts with 0 and 1, while an earlier recursive exercise numbers its first two terms as 1 and 1. The recurrence can match while indexing differs.

Optimize an answer

Not all states count ways. In the binary-tree problem, define best[v] as the largest sum on a downward path beginning at node v and ending at a leaf. A leaf contributes its own value. An internal node contributes its value plus the larger answer among its children.

The tree is supplied by levels. Process the last level first and combine children upward. If a level uses zero-based positions, the children of position j are at positions 2*j and 2*j+1 in the next level. Keep one indexing convention throughout the calculation.

Common mistakes and practice

Write the state meaning in a sentence before writing an array. Initialize only justified base cases. Check that transitions do not read negative indices accidentally: Python accepts negative indices and reads from the end of a list, which can hide a bug.

The exercises cover Fibonacci, staircase counts, a maximum tree path, and tiling. For tiling, classify the last tile by its length. Use the empty board as a base case and ignore choices longer than the current board.

Compare your table against direct enumeration for tiny inputs. If the values disagree, inspect what is being counted before changing arithmetic. Accepted output is useful evidence, but a clear state and transition explain why the method remains correct beyond the samples.