DSA

Dynamic Programming

Interview Prep · 8 entries

Memoization vs Tabulation

syntax

Memoization (top-down): Recursive + cache results of subproblems.
Tabulation (bottom-up): Iterative + fill a table from base cases up.
Both avoid recomputing overlapping subproblems.

example

// JavaScript — Fibonacci both ways
// Top-down (memoization)
function fibMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (n in memo) return memo[n];
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

// Bottom-up (tabulation)
function fibTab(n) {
  if (n <= 1) return n;
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

# Python
# Top-down
def fib_memo(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

# Bottom-up
def fib_tab(n):
    if n <= 1:
        return n
    dp = [0, 1]
    for i in range(2, n + 1):
        dp.append(dp[-1] + dp[-2])
    return dp[n]

output

fib_memo(10) → 55
fib_tab(10) → 55

Note Both are O(n) time, O(n) space. Memoization is easier to write (natural recursion) but has call stack overhead. Tabulation avoids stack overflow and can be space-optimized (keep only last 2 values → O(1) space). Start with memoization in interviews, then optimize to tabulation if asked.

memoizationtabulationtop-downbottom-updynamic programming introfibonacci

Climbing Stairs

syntax

You can take 1 or 2 steps. How many distinct ways to reach step n?
Recurrence: ways(n) = ways(n-1) + ways(n-2)
Base: ways(0) = 1, ways(1) = 1

example

// JavaScript
function climbStairs(n) {
  if (n <= 2) return n;
  let prev2 = 1, prev1 = 2;
  for (let i = 3; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }
  return prev1;
}

# Python
def climb_stairs(n):
    if n <= 2:
        return n
    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

output

climb_stairs(5) → 8 (paths: 11111, 1112, 1121, 1211, 2111, 122, 212, 221)

Note Time O(n), Space O(1) with the two-variable optimization. This is literally Fibonacci shifted by one index. Classic DP warm-up — if you see this, solve it fast and mention the Fibonacci connection. Generalize to k steps: dp[i] = sum of dp[i-1]...dp[i-k].

climbing stairsstaircase problemfibonacci variantways to reach top

Coin Change — Minimum Coins

syntax

dp[amount] = minimum coins needed to make that amount.
dp[0] = 0
For each amount, try each coin: dp[amount] = min(dp[amount], dp[amount - coin] + 1)

example

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

# Python
def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a and dp[a - coin] != float('inf'):
                dp[a] = min(dp[a], dp[a - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

output

coin_change([1,5,10,25], 30) → 2 (25 + 5)
coin_change([2], 3) → -1 (impossible)

Note Time O(amount * numCoins), Space O(amount). Greedy (always pick largest coin) does NOT work for all coin sets — DP is needed. Variant: number of ways to make change (count combinations instead of minimize). Return -1 if amount cannot be formed.

coin changeminimum coinsmaking changeDP coinunbounded knapsack

Longest Common Subsequence (LCS)

syntax

2D DP: dp[i][j] = LCS length of first i chars of s1 and first j chars of s2.
If s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

example

// JavaScript
function longestCommonSubsequence(s1, s2) {
  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];
}

# Python
def longest_common_subsequence(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[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]

output

longest_common_subsequence('abcde', 'ace') → 3 ('ace')

Note Time O(m*n), Space O(m*n), reducible to O(min(m,n)) with rolling array. To reconstruct the actual subsequence, backtrack through the DP table. LCS is the foundation for diff algorithms and edit distance. Subsequence ≠ substring (subsequence elements need not be contiguous).

longest common subsequenceLCS2D DPsubsequence matching

0/1 Knapsack

syntax

Given items with weight and value, maximize value within capacity.
Each item can be taken or left (0 or 1 times).
dp[i][w] = max value using first i items with capacity w.

example

// JavaScript
function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () =>
    new Array(capacity + 1).fill(0)
  );
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      dp[i][w] = dp[i - 1][w]; // skip item
      if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(
          dp[i][w],
          dp[i - 1][w - weights[i - 1]] + values[i - 1]
        );
      }
    }
  }
  return dp[n][capacity];
}

# Python
def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1])
    return dp[n][capacity]

output

knapsack([2,3,4,5], [3,4,5,6], 5) → 7 (items with weight 2+3, value 3+4)

Note Time O(n * capacity), Space O(n * capacity), reducible to O(capacity) with 1D DP (iterate weights backwards). The 0/1 constraint means we look at dp[i-1] (previous row). For unbounded knapsack (items reusable), look at dp[i] (current row). Recognize the pattern: subset selection with a constraint.

knapsack0/1 knapsacksubset selectionmaximize valuecapacity constraint

Longest Increasing Subsequence (LIS)

syntax

dp[i] = length of LIS ending at index i.
For each i, check all j < i: if arr[j] < arr[i], dp[i] = max(dp[i], dp[j] + 1).
Optimal: patience sorting with binary search → O(n log n).

example

// JavaScript — O(n^2) DP
function lisDP(arr) {
  const dp = new Array(arr.length).fill(1);
  for (let i = 1; i < arr.length; i++) {
    for (let j = 0; j < i; j++) {
      if (arr[j] < arr[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
  return Math.max(...dp);
}

// O(n log n) with binary search
function lisBinarySearch(arr) {
  const tails = [];
  for (const num of arr) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = lo + Math.floor((hi - lo) / 2);
      if (tails[mid] < num) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = num;
  }
  return tails.length;
}

# Python — O(n log n)
import bisect

def lis(arr):
    tails = []
    for num in arr:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)

output

lis([10,9,2,5,3,7,101,18]) → 4 (subsequence: 2,3,7,101 or 2,5,7,101)

Note O(n^2) DP is straightforward. O(n log n) uses a 'tails' array: tails[i] = smallest tail element for all increasing subsequences of length i+1. The tails array is NOT the actual LIS. To reconstruct, keep a parent pointer array. This is a very popular hard DP problem.

longest increasing subsequenceLISpatience sortingDP binary searchsubsequence length

Edit Distance (Levenshtein Distance)

syntax

Minimum operations (insert, delete, replace) to transform s1 into s2.
dp[i][j] = edit distance for s1[0..i-1] and s2[0..j-1].
If chars match: dp[i][j] = dp[i-1][j-1]
Else: 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

example

// JavaScript
function editDistance(s1, s2) {
  const m = s1.length, n = s2.length;
  const dp = Array.from({ length: m + 1 }, (_, i) =>
    Array.from({ length: n + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 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];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],     // delete
          dp[i][j - 1],     // insert
          dp[i - 1][j - 1]  // replace
        );
      }
    }
  }
  return dp[m][n];
}

# Python
def edit_distance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

output

edit_distance('horse', 'ros') → 3 (horse→rorse→rose→ros)

Note Time O(m*n), Space O(m*n), reducible to O(min(m,n)). Base cases: transforming empty string to s requires len(s) operations. Used in spell checkers, DNA analysis, and fuzzy matching. To reconstruct the operations, backtrack through the DP table.

edit distanceLevenshtein distancestring transformationminimum operationsword distance

House Robber (Maximum Non-Adjacent Sum)

syntax

Cannot rob two adjacent houses. Maximize total.
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
At each house: skip it (take prev best) or rob it (prev-prev best + current).

example

// JavaScript
function rob(nums) {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];
  let prev2 = 0, prev1 = 0;
  for (const num of nums) {
    const current = Math.max(prev1, prev2 + num);
    prev2 = prev1;
    prev1 = current;
  }
  return prev1;
}

# Python
def rob(nums):
    prev2, prev1 = 0, 0
    for num in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + num)
    return prev1

output

rob([2,7,9,3,1]) → 12 (rob houses 0,2,4: 2+9+1=12)

Note Time O(n), Space O(1). The circular variant (houses in a circle): run the algorithm twice — once excluding the first house, once excluding the last — and take the max. This pattern of 'take or skip' with constraints appears in many DP problems.

house robbermaximum non-adjacenttake or skipDP optimizationcircular variant