Dynamic ProgrammingTemplate 1 of 4

Dynamic ProgrammingIntermediateO(n) time, O(n) or O(1) space

1D Dynamic Programming

The Intuition

1D dynamic programming applies when the problem has two properties: optimal substructure (the answer for size i can be expressed in terms of answers for smaller sizes) and overlapping subproblems (the same smaller answers are reused many times). The technique is to compute every needed answer exactly once and store it in a table indexed by i.

The recipe has four steps that always apply:

Define the state. State the meaning of dp[i] in plain words: "the maximum profit using the first i houses," "the number of ways to reach step i," "the longest valid suffix ending at index i." A wrong state definition is the most common reason DP solutions fail.
Write the recurrence. Express dp[i] as a function of dp[i-1], dp[i-2], etc. Each transition encodes a decision (take or skip, advance one or two, etc.).
Set base cases. Fill in dp[0] (and sometimes dp[1]) directly. The recurrence does not apply at the boundary.
Iterate small to large. Compute dp[1], dp[2], ..., dp[n] in order. Every value is computed exactly once.

Two implementation styles compute the same answer:

Bottom-up (tabulation). Iterate for i in 1..n. Stack-safe, easier to reason about space.
Top-down (memoization). Recursive function with a cache. More natural when the recurrence is irregular or the natural traversal is from the top.

When dp[i] only depends on dp[i-1] and dp[i-2], the table can be reduced to two scalar variables, dropping space from O(n) to O(1). The classical examples are climbing stairs (LC 70), house robber (LC 198), and the Fibonacci-style recurrences. Problems where dp[i] depends on a wider window (longest increasing subsequence, word break) keep the full array.

When to use

Fibonacci-style problems, climbing stairs, house robber, coin change, longest increasing subsequence, word break, decode ways, or any problem with optimal substructure along one axis.

When NOT to use

Problem has no overlapping subproblems (use greedy)
State space is too large to memoize (use approximation)
Problem requires exploring all possibilities (use backtracking)

Pattern Recognition

Problem asks to count ways to reach a target stateProblem involves finding min cost path along a sequenceProblem requires making a decision at each step (take or skip)

Edge Cases

Base case with n = 0 or n = 1
Single element array
No valid solution exists (return -1 or 0)

Practice Problems

EasyClimbing Stairs

MediumHouse Robber

MediumCoin Change

MediumLongest Increasing Subsequence

MediumWord Break

Key Points

•Define state: dp[i] = optimal answer considering first i elements
•Find recurrence: dp[i] = f(dp[i-1], dp[i-2], ...)
•Identify base cases: dp[0], dp[1], etc.
•Optimize space if dp[i] only depends on a constant number of previous states
•Bottom-up (tabulation) avoids recursion overhead; top-down (memoization) is more intuitive

Code Template

def climb_stairs(n):
    """Number of ways to climb n stairs (1 or 2 steps)."""
    if n <= 2:
        return n
    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    return prev1

def house_robber(nums):
    """Maximum sum of non-adjacent elements."""
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    prev2, prev1 = 0, nums[0]
    for i in range(1, len(nums)):
        curr = max(prev1, prev2 + nums[i])
        prev2, prev1 = prev1, curr
    return prev1

def longest_increasing_subsequence(nums):
    """Length of LIS using DP + binary search (O(n log n))."""
    from bisect import bisect_left
    tails = []
    for num in nums:
        pos = bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)

func climbStairs(n int) int {
    // Number of ways to climb n stairs (1 or 2 steps).
    if n <= 2 {
        return n
    }
    prev2, prev1 := 1, 2
    for i := 3; i <= n; i++ {
        curr := prev1 + prev2
        prev2, prev1 = prev1, curr
    }
    return prev1
}

func houseRobber(nums []int) int {
    // Maximum sum of non-adjacent elements.
    if len(nums) == 0 {
        return 0
    }
    if len(nums) == 1 {
        return nums[0]
    }
    prev2, prev1 := 0, nums[0]
    for i := 1; i < len(nums); i++ {
        curr := prev1
        if prev2+nums[i] > curr {
            curr = prev2 + nums[i]
        }
        prev2, prev1 = prev1, curr
    }
    return prev1
}

public int climbStairs(int n) {
    // Number of ways to climb n stairs (1 or 2 steps).
    if (n <= 2) return n;
    int prev2 = 1, prev1 = 2;
    for (int i = 3; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

public int houseRobber(int[] nums) {
    // Maximum sum of non-adjacent elements.
    if (nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];
    int prev2 = 0, prev1 = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int curr = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

public int longestIncreasingSubsequence(int[] nums) {
    // Length of LIS using DP + binary search O(n log n).
    List<Integer> tails = new ArrayList<>();
    for (int num : nums) {
        int pos = Collections.binarySearch(tails, num);
        if (pos < 0) pos = -(pos + 1);
        if (pos == tails.size()) tails.add(num);
        else tails.set(pos, num);
    }
    return tails.size();
}

Common Mistakes

Wrong base case initialization
Off-by-one errors in the recurrence
Not considering all transitions in the recurrence relation

Related Patterns

CrackingWalnuts