DP Fundamentals

Opening scenario

Problem references use LC for LeetCode.

Two warm-ups an interviewer chains together to see if you can derive DP, not just recite it. First: compute the n-th Fibonacci number efficiently. Then: there are n houses in a row, each painted red, blue, or green. costs[i][k] is the cost to paint house i color k. No two adjacent houses may share a color. Return the minimum total cost (LC 256, Paint House). How you move from Fibonacci to Paint House is exactly the reasoning DP interviews test.

Use fib(0) = 0, fib(1) = 1, and fib(n) = fib(n-1) + fib(n-2) for n ≥ 2. In Paint House, colors are indexed 0, 1, and 2, and an empty list of houses costs 0. Start by deciding what information from a smaller problem is enough to solve the next one.

Question progression

Q1 — Memoized fib is already fast. So what is dynamic programming?

Question: You memoized Fibonacci to O(n). Did you…