Dynamic Programming Patterns Explained: A Visual Guide

Dynamic Programming (DP) has a reputation for being the hardest topic in coding interviews. But here is a secret: most DP problems fall into one of a few patterns. Once you learn these patterns, DP becomes much more approachable. You stop asking "how do I solve this DP problem?" and start asking "which DP pattern does this problem follow?"

This guide covers the 6 core DP patterns available in AlgoArk. For each, we explain the idea, the key recurrence, an example problem, and how to identify it.

// Climbing Stairs
function climbStairs(n: number): number {
  let prev2 = 1, prev1 = 1;
  for (let i = 2; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

// 0/1 Knapsack (1D optimization)
function knapsack(weights: number[], values: number[], W: number): number {
  const dp = new Array(W + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let w = W; w >= weights[i]; w--) {  // reverse!
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  return dp[W];
}

// Coin Change (minimum coins)
function coinChange(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (const coin of coins) {
    for (let a = coin; a <= amount; a++) {  // forward!
      dp[a] = Math.min(dp[a], dp[a - coin] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

// Longest Common Subsequence
function lcs(s1: string, s2: string): number {
  const m = s1.length, n = s2.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 (s1[i - 1] === s2[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];
}

// Binary Tree Maximum Path Sum
let globalMax = -Infinity;

function maxPathDown(node: TreeNode | null): number {
  if (!node) return 0;
  const left = Math.max(0, maxPathDown(node.left));
  const right = Math.max(0, maxPathDown(node.right));

  // Path through this node (cannot extend further up)
  globalMax = Math.max(globalMax, left + right + node.val);

  // Best single-side path (can extend to parent)
  return Math.max(left, right) + node.val;
}

// Minimum Path Sum
function minPathSum(grid: number[][]): number {
  const m = grid.length, n = grid[0].length;
  const dp = Array.from({ length: m }, () => new Array(n).fill(0));

  dp[0][0] = grid[0][0];
  for (let i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
  for (let j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
    }
  }
  return dp[m-1][n-1];
}

How to Identify Which DP Pattern to Use

When you encounter a DP problem, ask yourself these questions:

Common DP Mistakes

• Confusing 0/1 and Unbounded Knapsack: The difference is whether items can be reused. In code, 0/1 iterates weights in reverse; unbounded iterates forward.
• Using DP when Greedy works: Not all optimization problems need DP. If the problem has a greedy choice property (locally optimal = globally optimal), use Greedy instead.
• Forgetting base cases: Every DP solution needs clear base cases. For Fibonacci: dp[0] = dp[1] = 1. For Knapsack: dp[0] = 0. Missing or wrong base cases break everything.
• Not optimizing space: Many 2D DP solutions can be reduced to 1D because each row only depends on the previous row. This is a common follow-up question in interviews.

Study Order

If you are starting from scratch, study the DP patterns in this order:

1. Fibonacci — Build DP intuition with the simplest pattern
2. Grid DP — Visually intuitive; see the DP table on the grid
3. 0/1 Knapsack — The foundation of subset-selection problems
4. Unbounded Knapsack — Small twist on 0/1; master the forward vs. reverse distinction
5. LCS — Two-sequence problems with 2D DP
6. DP on Trees — Combines tree traversal with DP; the most advanced pattern

For each pattern, solve 3-5 problems before moving on. Use our Decision Tree to check if you are identifying the right pattern, and the Quiz to test your recognition skills.

Related reads:

• Top 10 LeetCode Patterns Every FAANG Candidate Must Know
• BFS vs DFS: When to Use Which
• Two Pointers vs Sliding Window: When to Use Each