Dynamic programming

Dynamic programming solves a problem by building it up from smaller versions of itself, and saving each answer so you only work it out once. It works when the same subproblems keep coming up, and the best overall answer is made from the best answers to the pieces.

1. Decide on the state. What does each saved value mean?
2. Write the transition. How do you get it from smaller states?
3. Set the base cases.
4. Pick an order so everything a state needs is ready before you get to it.

Take the fewest coins needed to make an amount. The state is the best answer for each total, and each coin is one way to get there:

def fewest_coins(coins, amount):
    best = [0] + [float("inf")] * amount
    for total in range(1, amount + 1):
        for coin in coins:
            if coin <= total:
                best[total] = min(best[total], best[total - coin] + 1)
    return -1 if best[amount] == float("inf") else best[amount]

• Look for "minimum," "maximum" or "how many ways."
• Say what your DP value means in one sentence before you code.
• Your time is the number of states times the work for each one.

Robbing houses on a street

Houses on a street have money in them, like [2, 7, 9, 3, 1]. You can't take from two houses next to each other. What's the most you can get?

1. Greedy doesn't work. With [3, 4, 3], taking the biggest house first gets you 4, but skipping it gets you 3 + 3 = 6.
2. State: best[i] is the most you can get from the first i houses.
3. Transition: for house i, either skip it, giving best[i - 1], or take it, giving best[i - 2] + money[i]. Take the bigger one.
4. Base cases: best[0] = 0 with no houses, best[1] = money[0].
5. For [2, 7, 9, 3, 1]: 0, 2, 7, 11, 11, 12. The answer is 12.
6. Each state only needs the two before it, so you can keep two variables instead of a whole list. That's O(n) time and O(1) space.
7. If they ask which houses, keep the table, then walk it backward and check which choice made each value.

Things interviewers tend to ask once you've brought this up.

What if the houses are in a circle?

The first and last are now neighbors. Solve it twice, once without the first house and once without the last, and take the better one.

What's the longest common subsequence of two strings?

State is (i, j): the best for the first i characters of one and the first j of the other. If they match, 1 + (i - 1, j - 1). Otherwise the best of dropping one character from either side.

How do you do DP on a tree?

Each node returns its best answer for each situation, like with and without the node included, and its parent combines its children's answers.

How do you tell DP from backtracking?

If you need every solution, it's backtracking. If you need a count or a best value, and the same subproblems come up again, it's DP.

• Jumping into code before defining the state in words.
• Making the state too small, so it doesn't capture something that matters, like whether you used the last item.
• Wrong base cases, especially for empty input.
• Filling the table in an order where some states aren't ready yet.
• Getting the right number but forgetting they asked for the actual choices too.

• Graph traversal and shortest pathsBFS, DFS and Dijkstra, and when to use each.
• Binary searchCut the search in half, even when you're searching for an answer.
• Heaps and priority queuesAlways have the smallest or largest item ready.