Skip to content
Coding Patterns - Guide to 30 Core Algorithm Patterns
Dynamic Programming: Complete Guide to Memoization
Dynamic Programming: Practice Problems with Solutions

Dynamic Programming: Practice Problems with Solutions

Welcome to the practice problems for dynamic programming. If you need a refresher on the code, the code templates have the memoization and tabulation blueprints in all 6 languages. Each problem below includes a hint, a visual walkthrough, and the full solution.

Recommended Study Order

Work through the problems in the order listed. Each one adds one new idea on top of the previous ones, and skipping ahead usually means fighting two new concepts at once.

  1. Min Cost Climbing Stairs teaches the 1D state, the cache, and the base cases in their purest form. Nothing else competes for your attention.
  2. House Robber adds a choice at each state and then shows the space optimization down to two variables.
  3. Decode Ways keeps the same 1D shape but makes you validate every transition against the input before using it.
  4. Longest Increasing Subsequence is the first problem where a state reads every earlier state, which turns the cost into
    O(N^2)
    .
  5. Longest Common Subsequence turns the table into a grid, because two inputs means two indices.
  6. Regular Expression Matching keeps the grid and adds wildcards, and the recurrence branches in a way that nothing else in this set does.
The order above is designed to build intuition progressively. The app schedules your reviews so you don’t forget the Easy patterns while grinding Hard ones. Set up your review schedule .

Easy Problems

1. Min Cost Climbing Stairs

LeetCode 746 | Difficulty: Easy

  • Brief: Each step of a staircase has a cost, and you can climb one or two steps at a time. Find the cheapest way to reach the top.
  • Why this pattern: The cheapest way from step i depends only on the cheapest ways from i+1 and i+2, so the state is a single index and the recurrence writes itself.
  • Key Insight: The answer is not the cost of the last step. You can skip it entirely by jumping from the second-to-last step, so return the minimum of the last two states.

Visual:

    graph TD
    A["cost: 10 15 20"] --> B["stand on step 0 costs 10"]
    A --> C["stand on step 1 costs 15"]
    B --> D["step 2: 20 + min(10, 15) = 30"]
    D --> E["finish: min(15, 30) = 15"]
    C --> E
    E --> F["return 15"]

Code:

var minCostClimbingStairs = function(cost) {
    let prev2 = cost[0]; // cheapest way to stand on step 0
    let prev1 = cost[1]; // cheapest way to stand on step 1

    for (let i = 2; i < cost.length; i++) {
        // step i is reached from step i-1 or i-2, so the
        // cheapest path to i uses the cheaper of the two
        const current = Math.min(prev2, prev1) + cost[i];
        prev2 = prev1;
        prev1 = current;
    }

    // the top is reachable from the last step or the one before it
    return Math.min(prev2, prev1);
};

The two-variable version works because each state only reads the two states before it. The final return is the trickiest part: since the top has no cost, you take the minimum of the last two steps instead of the last one alone.

Medium Problems

2. House Robber

LeetCode 198 | Difficulty: Medium

  • Brief: Maximize the value robbed from houses in a line, with the rule that adjacent houses cannot both be robbed.
  • Why this pattern: At each house the state is the best total so far, and the transition is a choice: rob this house and add the total from two houses back, or skip it and keep the total from the previous house.
  • Key Insight: The constraint never forces you to look further back than two houses. If the last two best totals are correct, the next one is correct, which is exactly what makes the two-variable version valid.

Visual:

    graph LR
    A["nums: 2 7 9 3 1"] --> B["house 0: rob 2, best 2"]
    B --> C["house 1: rob 7, best 7"]
    C --> D["house 2: 9 + 2 = 11, best 11"]
    D --> E["house 3: 3 + 7 = 10, keep 11"]
    E --> F["house 4: 1 + 11 = 12, best 12"]

Code:

var rob = function(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;
};

The empty-house edge case returns 0 before the loop, because nums[0] does not exist. The recurrence itself is the same shape as Min Cost Climbing Stairs, but the transition is a max over a choice instead of a min over two forced paths.

3. Decode Ways

LeetCode 91 | Difficulty: Medium

  • Brief: Count the ways to decode a digit string, where A is 1 through Z is 26, and each digit or valid two-digit pair is one letter.
  • Why this pattern: The number of ways to decode a prefix is the sum of ways for the previous one or two prefixes, but only when the corresponding digit or pair actually maps to a letter.
  • Key Insight: A leading zero invalidates a transition. The pair “06” maps to nothing, and a lone “0” maps to nothing, so each candidate transition must be checked before it contributes to the sum.

Visual:

    graph LR
    A["dp[0] = 1: empty prefix"] --> B["dp[1] = 1: '2' decodes as B"]
    B --> C["dp[2] = dp[1] + dp[0] = 2: '2|2', '22'"]
    C --> D["dp[3] = dp[2] + dp[1] = 3: '2|2|6', '22|6', '2|26'"]

Code:

var numDecodings = function(s) {
    if (s[0] === '0') return 0;

    let prev2 = 1; // ways for the empty prefix
    let prev1 = 1; // ways for the prefix of length 1

    for (let i = 2; i <= s.length; i++) {
        let current = 0;
        const one = Number(s[i - 1]);
        const two = Number(s.slice(i - 2, i));

        if (one !== 0) current += prev1;              // single digit
        if (two >= 10 && two <= 26) current += prev2; // two-digit pair
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
};

The base case is where counting problems differ from minimum problems. The empty prefix has exactly one decoding, which is why prev2 starts at 1 and not 0. Inputs like “100” collapse to 0 ways, because neither “00” nor “0” maps to a letter, and that is the correct answer rather than a bug.

4. Longest Increasing Subsequence

LeetCode 300 | Difficulty: Medium

  • Brief: Find the length of the longest strictly increasing subsequence in an array. Elements do not need to be contiguous.
  • Why this pattern: The longest run ending at index i is one more than the longest run ending at any earlier index j where nums[j] < nums[i], so every state depends on all earlier states.
  • Key Insight: Initialize every state to 1, because a single element is always a valid run of length one. The answer is the maximum over all states, not the last state.

Visual:

    graph TD
    A["nums: 10 9 2 5 3 7 101 18"] --> B["5: only 2 is smaller, run length 2"]
    B --> C["7: 2, 5, 3 are smaller, run length 3"]
    C --> D["101: every earlier value is smaller, run length 4"]
    D --> E["answer: 4, the run 2, 5, 7, 101"]

Code:

var lengthOfLIS = function(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;
};

Every transition is a look-back over all previous indices, which makes this

O(N^2)
time and
O(N)
space. There is a faster greedy plus binary search solution that runs in
O(N log N)
, but it does not build a DP table and it is a different pattern. Know this version first, because it transfers to many other problems.

5. Longest Common Subsequence

LeetCode 1143 | Difficulty: Medium

  • Brief: Find the length of the longest subsequence common to two strings. Characters do not need to be contiguous in either string.
  • Why this pattern: The answer for prefixes text1[0..i] and text2[0..j] depends on the same question for smaller prefixes, which makes a 2D table with two indices the natural state.
  • Key Insight: When the two characters match, the answer grows by one from the diagonal cell. When they differ, the answer carries over from the cell above or the cell to the left, whichever is larger.

Visual:

    graph TD
    A["text1 = abcde, text2 = ace"] --> B["a matches a, cell = 1"]
    B --> C["c matches c, cell = 2"]
    C --> D["e matches e, cell = 3"]
    D --> E["answer: 3"]

Code:

var longestCommonSubsequence = function(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];
};

The zero row and zero column are the base cases, and they do the work of “empty string” for you. Because each cell only reads the row above and the column to the left, the row-by-row fill order always has the dependencies ready. Edit Distance uses the same table with a min over three operations instead of a max over two.

Hard Problems

6. Regular Expression Matching

LeetCode 10 | Difficulty: Hard

  • Brief: Implement regex matching where . matches any single character and * matches zero or more of the preceding character. The whole string must match the whole pattern.
  • Why this pattern: Whether prefixes s[0..i] and p[0..j] match is answered by smaller matching questions, and the * branch splits into “zero copies” and “one more copy”.
  • Key Insight: A * never matches on its own. It belongs to the character before it, so the zero-copy branch jumps back two pattern characters, and the one-or-more branch is only usable when the pattern character before the * matches the current string character.

Visual:

    graph LR
    A["s = aab, p = c*a*b"] --> B["c* matches zero c's"]
    B --> C["a* matches two a's"]
    C --> D["b matches b"]
    D --> E["dp[3][5] = true"]

Code:

var isMatch = function(s, p) {
    const m = s.length, n = p.length;
    const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));

    dp[0][0] = true; // two empty strings match

    // patterns like a*b* can match the empty string when each
    // star is read as "zero of the previous character"
    for (let j = 1; j <= n; j++) {
        if (p[j - 1] === '*') {
            dp[0][j] = dp[0][j - 2];
        }
    }

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p[j - 1] === '.' || p[j - 1] === s[i - 1]) {
                // a direct match consumes one character from each
                dp[i][j] = dp[i - 1][j - 1];
            } else if (p[j - 1] === '*') {
                // zero copies of the previous pattern character
                dp[i][j] = dp[i][j - 2];
                // one more copy, which consumes s[i - 1]
                if (p[j - 2] === '.' || p[j - 2] === s[i - 1]) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
            }
        }
    }

    return dp[m][n];
};

The empty-row initialization is what makes a* and a*b* match the empty string, and it is easy to forget. The * branch is the core of the problem: dp[i][j-2] covers the zero-copy case and dp[i-1][j] covers one more copy, and the OR of the two is what lets a single * handle any repetition count.

Hard problems are where patterns separate candidates who pass from candidates who get offers. Track your misses and review them on a spaced schedule so you do not repeat them in the real interview.

These six problems cover the full arc of dynamic programming. Start with the single-index state in Min Cost Climbing Stairs, add choices and validation in House Robber and Decode Ways, move to look-back and 2D tables in Longest Increasing Subsequence and Longest Common Subsequence, and finish with the wildcard branch in Regular Expression Matching. Once the state definition feels natural on all of these, the harder DP problems stop being about the code and start being about reading the problem.

Done with these problems? The app has more, plus a review system that brings problems back right before you would forget them. Continue your prep .