Dynamic Programming: Code Templates in 6 Languages

Coding Patterns - Guide to 30 Core Algorithm Patterns

Dynamic Programming: Complete Guide to Memoization

If you have not read the concept guide yet, start there for the state definition rules and complexity analysis. This page gives you the memoization and tabulation blueprints you can memorize and adapt in an interview. The main template is the recursive form with a cache. Each variation after it shows one way the same skeleton changes shape.

Main Template: Memoization (Top-Down)

This is the top-down form of dynamic programming. It solves the problem the same way the naive recursion would, but it stores every answer on the way out of the recursion so no state is computed twice. Each call checks the cache first, and the recursion only does real work on the first visit to a state.

Use this for Min Cost Climbing Stairs .

function minCostClimbingStairs(cost) {
    const memo = new Array(cost.length).fill(-1);

    // dfs(i) is the cheapest way to climb from step i to the top
    function dfs(i) {
        if (i >= cost.length) return 0; // past the top, nothing left to pay
        if (memo[i] !== -1) return memo[i]; // already paid this climb once

        memo[i] = cost[i] + Math.min(dfs(i + 1), dfs(i + 2));
        return memo[i];
    }

    // the top can be reached from step 0 or step 1
    return Math.min(dfs(0), dfs(1));
}

def min_cost_climbing_stairs(cost: List[int]) -> int:
    memo = [-1] * len(cost)

    def dfs(i: int) -> int:
        if i >= len(cost):
            return 0  # past the top, nothing left to pay
        if memo[i] != -1:
            return memo[i]  # already paid this climb once

        memo[i] = cost[i] + min(dfs(i + 1), dfs(i + 2))
        return memo[i]

    return min(dfs(0), dfs(1))

public int minCostClimbingStairs(int[] cost) {
    int[] memo = new int[cost.length];
    Arrays.fill(memo, -1);
    return Math.min(dfs(cost, memo, 0), dfs(cost, memo, 1));
}

private int dfs(int[] cost, int[] memo, int i) {
    if (i >= cost.length) return 0; // past the top, nothing left to pay
    if (memo[i] != -1) return memo[i]; // already paid this climb once

    memo[i] = cost[i] + Math.min(dfs(cost, memo, i + 1), dfs(cost, memo, i + 2));
    return memo[i];
}

int minCostClimbingStairs(vector<int>& cost) {
    vector<int> memo(cost.size(), -1);
    return min(dfs(cost, memo, 0), dfs(cost, memo, 1));
}

int dfs(const vector<int>& cost, vector<int>& memo, int i) {
    if (i >= cost.size()) return 0; // past the top, nothing left to pay
    if (memo[i] != -1) return memo[i]; // already paid this climb once

    memo[i] = cost[i] + min(dfs(cost, memo, i + 1), dfs(cost, memo, i + 2));
    return memo[i];
}

func minCostClimbingStairs(cost []int) int {
    memo := make([]int, len(cost))
    for i := range memo {
        memo[i] = -1
    }

    var dfs func(int) int
    dfs = func(i int) int {
        if i >= len(cost) {
            return 0 // past the top, nothing left to pay
        }
        if memo[i] != -1 {
            return memo[i] // already paid this climb once
        }

        memo[i] = cost[i] + min(dfs(i+1), dfs(i+2))
        return memo[i]
    }

    return min(dfs(0), dfs(1))
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

def min_cost_climbing_stairs(cost)
    memo = Array.new(cost.length, -1)

    dfs = lambda do |i|
        return 0 if i >= cost.length # past the top, nothing left to pay
        return memo[i] if memo[i] != -1 # already paid this climb once

        memo[i] = cost[i] + [dfs.call(i + 1), dfs.call(i + 2)].min
    end

    [dfs.call(0), dfs.call(1)].min
end

Templates only help if you can recall them without staring at the screen. Turn these snippets into flashcards for daily mobile review.

Code Breakdown

Key Variables

i: the state. The step you are standing on. Everything before step i is already paid for and does not affect the rest of the climb.
cost[i]: the price of standing on step i. It is paid exactly once per path, when that step is reached.
memo: the cache. memo[i] holds the cheapest climb from step i after the first computation. The -1 sentinel means “not computed yet”.
dfs(i): the recurrence. The cheapest way from step i to the top is cost[i] plus the cheaper of the two steps ahead.

Visual Mechanism

    graph TD
    A["dfs(i)"] --> B{"i >= n?"}
    B -->|Yes| Z["return 0"]
    B -->|No| C{"memo[i] set?"}
    C -->|Yes| Y["return memo[i]"]
    C -->|No| D["compute cost[i] + min(dfs(i+1), dfs(i+2))"]
    D --> E["store result in memo[i]"]
    E --> Y

Critical Sections

The base case is i >= cost.length, which returns 0. Standing past the top costs nothing, and it is the only state that never needs the cache.

The cache check happens before any work. That single guard is what separates DP from the exponential recursion. The same function body runs, but each state is solved once and every repeat visit is a lookup.

The recurrence reads the two future states and stores the result before returning. The answer for the whole problem is min(dfs(0), dfs(1)), because the top can be reached from either starting step.

Variations

1. Tabulation (Bottom-Up)

When the recursion shape is simple, you can drop the cache and fill the table directly in dependency order. This version computes the same costs but walks backward from the top, so every state reads two already-final neighbors.

Time

O(N)

, space

O(N)

Use this for Min Cost Climbing Stairs .

function minCostClimbingStairs(cost) {
    const n = cost.length;
    const dp = new Array(n + 2).fill(0);

    // dp[i] is the cheapest way from step i to the top.
    // Fill backward so each step reads the two steps ahead,
    // which are already final.
    for (let i = n - 1; i >= 0; i--) {
        dp[i] = cost[i] + Math.min(dp[i + 1], dp[i + 2]);
    }

    return Math.min(dp[0], dp[1]);
}

def min_cost_climbing_stairs(cost: List[int]) -> int:
    n = len(cost)
    dp = [0] * (n + 2)  # dp[i] = cheapest way from step i to the top

    # fill backward so dp[i] can read dp[i+1] and dp[i+2]
    for i in range(n - 1, -1, -1):
        dp[i] = cost[i] + min(dp[i + 1], dp[i + 2])

    return min(dp[0], dp[1])

    graph LR
    A["dp[n] = dp[n+1] = 0"] --> B["i from n-1 down to 0"]
    B --> C["dp[i] = cost[i] + min(dp[i+1], dp[i+2])"]
    C --> D["answer: min(dp[0], dp[1])"]

2. Space-Optimized (Two Variables)

Once you notice that state i only reads states i-1 and i-2, the full table is wasteful. Two rolling variables carry the same information. This is the shape behind most 1D problems, and it is what interviewers mean when they ask for the space-optimized solution.

Time

O(N)

, space

O(1)

Use this for House Robber .

function rob(nums) {
    if (nums.length === 0) return 0;

    let prev2 = 0;       // best total two houses back
    let prev1 = nums[0]; // best total up to the previous house

    for (let i = 1; i < nums.length; i++) {
        // rob i: prev2 + nums[i]. skip i: keep prev1.
        const current = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

def rob(nums: List[int]) -> int:
    if not nums:
        return 0

    prev2, prev1 = 0, nums[0]  # best two houses back, best so far

    for i in range(1, len(nums)):
        # robbing i forces skipping i-1, so compare prev2 + nums[i]
        # against the best total that already skipped i
        current = max(prev1, prev2 + nums[i])
        prev2, prev1 = prev1, current

    return prev1

    graph LR
    A["prev2: best up to i-2"] --> B["prev1: best up to i-1"]
    B --> C["current = max(prev1, prev2 + nums[i])"]
    C --> D["shift: prev2 = prev1, prev1 = current"]

3. Look-Back (O(N^2))

Some states depend on every earlier state, not just the previous two. Each dp[i] scans all j < i and extends the best run that can accept nums[i]. The table is still 1D, but every cell does linear work, which is where the quadratic bound comes from.

Time

O(N^2)

, space

O(N)

Use this for Longest Increasing Subsequence .

function lengthOfLIS(nums) {
    const dp = new Array(nums.length).fill(1);
    let best = 1;

    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                // nums[i] extends the increasing run ending at j
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        best = Math.max(best, dp[i]);
    }
    return best;
}

    graph TD
    A["for each i, dp[i] starts at 1"] --> B["for each j < i"]
    B --> C{"nums[j] < nums[i]?"}
    C -->|Yes| D["dp[i] = max(dp[i], dp[j] + 1)"]
    C -->|No| E["next j"]
    D --> E
    E --> F["track the best dp[i] seen"]

4. Two-Dimensional Table

Two inputs mean two indices, and the table becomes a grid. Each cell reads its diagonal, its left neighbor, and its upper neighbor. This is the shape of longest common subsequence, edit distance, and every two-string DP problem.

Time

O(N^2)

, space

O(N^2)

Use this for Longest Common Subsequence .

function longestCommonSubsequence(text1, text2) {
    const m = text1.length, n = text2.length;
    const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                // a matching pair extends the best prefix of both
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                // no match: keep the longer best prefix from
                // either text1 or text2
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

def longest_common_subsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                # a matching pair extends the best prefix of both
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                # no match: keep the longer best prefix from
                # either text1 or text2
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

func longestCommonSubsequence(text1 string, text2 string) int {
    m, n := len(text1), len(text2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if text1[i-1] == text2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[m][n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

def longest_common_subsequence(text1, text2)
    m, n = text1.length, text2.length
    dp = Array.new(m + 1) { Array.new(n + 1, 0) }

    (1..m).each do |i|
        (1..n).each do |j|
            if text1[i - 1] == text2[j - 1]
                dp[i][j] = dp[i - 1][j - 1] + 1
            else
                dp[i][j] = [dp[i - 1][j], dp[i][j - 1]].max
            end
        end
    end

    dp[m][n]
end

    graph TD
    A["dp[i][j]"] --> B{"text1[i-1] == text2[j-1]?"}
    B -->|Yes| C["dp[i-1][j-1] + 1"]
    B -->|No| D["max(dp[i-1][j], dp[i][j-1])"]

Constraint DP (Knapsack)

If the problem adds a capacity or a target sum, the state gains a second dimension for the remaining budget. That shape is distinct enough to have its own pattern page. The Knapsack templates cover the 0/1 and unbounded variants with full code in all 6 languages.

Each variation above is a separate review card in the app. Drill them individually so you don’t mix up the conditions under pressure.

Now head to the practice problems to apply these templates to real interview questions.

Now that you have the templates, the next step is application. Head to the practice problems or start reviewing these templates with spaced repetition .