1-D Dynamic Programming

How it works

Dynamic programming is recursion that refuses to solve the same subproblem twice. If a brute-force recursion branches into calls whose arguments repeat, store each answer the first time and look it up afterwards. That is memoization; filling a table in order is the same idea bottom-up.

In one-dimensional DP the state is a single index: the best answer for the first i items, or for a target value i. Everything hinges on writing the recurrence: how dp[i] is built from a few earlier entries. Say it in words first: 'the best up to house i is either skipping house i or robbing it plus the best up to i - 2'.

The recurrence works when the problem has optimal substructure, meaning the best answer for i really is assembled from best answers for smaller inputs, and when the number of distinct states is small enough to tabulate.

Look for 'number of ways', 'minimum cost', 'maximum value', or 'is it possible' over a sequence where each step makes a small choice. Climbing stairs, house robbing, coin change, word break and longest increasing subsequence all fit.

How to attack it

1. 1Define dp[i] in one precise sentence.
2. 2Write the recurrence from the last choice made at i.
3. 3Set the base cases and the iteration order so dependencies are ready.
4. 4Decide where the answer lives (dp[n], or the max over all i).
5. 5Shrink the table to a few variables if dp[i] only uses the last few entries.

Template

A skeleton to adapt, not a solution to paste. Write it from memory a few times.

from functools import lru_cache


def max_non_adjacent(nums):
    # dp[i] = best total using items 0..i-1.
    # dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]); only two values are needed.
    prev2, prev1 = 0, 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1


def min_coins(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount          # dp[a] = fewest coins to make a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1


def ways_top_down(n):
    @lru_cache(maxsize=None)            # memoization: each n solved once
    def go(i):
        if i <= 1:
            return 1
        return go(i - 1) + go(i - 2)
    return go(n)

What it costs