Back to blog

Dynamic Programming & Greedy Algorithms: Complete Guide

algorithmsdynamic-programminggreedyinterview-prepdsaoptimization
Dynamic Programming & Greedy Algorithms: Complete Guide

Introduction

Dynamic Programming and Greedy Algorithms are the two major paradigms for solving optimization problems — finding the best, cheapest, longest, shortest, or most efficient solution. They're also among the most feared topics in coding interviews.

Here's the good news: both paradigms follow a pattern. DP breaks a problem into overlapping subproblems and stores results to avoid redundant work. Greedy makes the locally optimal choice at each step, trusting that local optimality leads to global optimality. Once you internalize these patterns, problems that seemed impossible start clicking.

In coding interviews, DP problems appear in roughly 25-30% of technical interviews. They're considered the hardest category — but they're also the most formulaic. This post gives you a systematic framework to tackle any DP problem, plus a clear understanding of when greedy is the right (and simpler) approach.

This is the final post in our DSA series. Everything you've learned — arrays, linked lists, trees, graphs, heaps, sorting — comes together here. DP and greedy algorithms build on all those data structures.

What You'll Learn

✅ Understand when to use DP vs greedy vs brute force
✅ Master the 5-step DP framework for any problem
✅ Implement memoization (top-down) and tabulation (bottom-up)
✅ Solve 1D and 2D DP problems systematically
✅ Recognize common DP patterns (knapsack, subsequence, grid, string)
✅ Understand greedy choice property and when greedy works
✅ Solve 10 classic DP + 4 greedy interview problems step-by-step

Prerequisites

1. Dynamic Programming Fundamentals

1.1 What Is Dynamic Programming?

Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them into overlapping subproblems, solving each subproblem once, and storing the result for future use.

Think of it as recursion + caching. Without DP, a recursive solution recomputes the same subproblems exponentially. With DP, each subproblem is solved once and reused.

In the tree above, fib(3) and fib(2) are computed multiple times. DP eliminates this redundancy.

1.2 Two Conditions for DP

A problem can be solved with DP if it has:

  1. Overlapping subproblems: The same smaller problems are solved repeatedly
  2. Optimal substructure: The optimal solution to the problem can be built from optimal solutions of its subproblems
ConditionWhat It MeansExample
Overlapping subproblemsSame computation repeatedFibonacci: fib(3) computed many times
Optimal substructureOptimal answer uses optimal sub-answersShortest path: shortest A→C uses shortest A→B + B→C

1.3 Memoization vs Tabulation

ApproachDirectionImplementationProsCons
MemoizationTop-downRecursion + cache (hashmap/array)Intuitive, only solves needed subproblemsStack overflow risk, function call overhead
TabulationBottom-upIterative, fill table from base casesNo recursion overhead, easy to optimize spaceMust solve all subproblems, order matters

Rule of thumb: Start with memoization (easier to think about), then convert to tabulation if needed for optimization.

1.4 The 5-Step DP Framework

Every DP problem follows this systematic approach:

  1. Define the state — What does dp[i] (or dp[i][j]) represent?
  2. Define recurrence relation — How to compute dp[i] from previously computed states?
  3. Identify base cases — What are the trivially solvable smallest subproblems?
  4. Decide computation order — Top-down (memoization) or bottom-up (tabulation)?
  5. Optimize space — Can you reduce from 2D to 1D? From array to two variables?

2. 1D Dynamic Programming

Problem 1: Climbing Stairs

You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. How many distinct ways can you reach the top?

5-step framework:

  1. State: dp[i] = number of ways to reach step i
  2. Recurrence: dp[i] = dp[i-1] + dp[i-2] (come from 1 step back or 2 steps back)
  3. Base cases: dp[0] = 1, dp[1] = 1
  4. Order: Bottom-up (0 → n)
  5. Space optimization: Only need previous two values → O(1) space
// TypeScript - Climbing Stairs
// Memoization (top-down)
function climbStairsMemo(n: number): number {
  const memo = new Map<number, number>();
 
  function dp(i: number): number {
    if (i <= 1) return 1;
    if (memo.has(i)) return memo.get(i)!;
 
    const result = dp(i - 1) + dp(i - 2);
    memo.set(i, result);
    return result;
  }
 
  return dp(n);
}
 
// Tabulation (bottom-up)
function climbStairsTab(n: number): number {
  if (n <= 1) return 1;
  const dp = new Array(n + 1);
  dp[0] = 1;
  dp[1] = 1;
 
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
 
  return dp[n];
}
 
// Space-optimized
function climbStairs(n: number): number {
  if (n <= 1) return 1;
  let prev2 = 1, prev1 = 1;
 
  for (let i = 2; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
 
  return prev1;
}
 
console.log(climbStairs(5)); // 8
# Python - Climbing Stairs
from functools import lru_cache
 
# Memoization (top-down)
def climb_stairs_memo(n: int) -> int:
    @lru_cache(maxsize=None)
    def dp(i: int) -> int:
        if i <= 1:
            return 1
        return dp(i - 1) + dp(i - 2)
    return dp(n)
 
# Tabulation (bottom-up)
def climb_stairs_tab(n: int) -> int:
    if n <= 1:
        return 1
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
 
# Space-optimized
def climb_stairs(n: int) -> int:
    if n <= 1:
        return 1
    prev2, prev1 = 1, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1
 
print(climb_stairs(5))  # 8

Time: O(n). Space: O(1) optimized.

Problem 2: House Robber

You are a robber planning to rob houses along a street. Each house has money. You cannot rob two adjacent houses. What is the maximum money you can rob?

5-step framework:

  1. State: dp[i] = max money robbing from houses 0..i
  2. Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — skip house i, or rob it (+ skip i-1)
  3. Base cases: dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
  4. Order: Bottom-up (0 → n)
  5. Space: O(1) — only need two previous values
// TypeScript - House Robber
function rob(nums: number[]): number {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];
 
  let prev2 = nums[0];
  let prev1 = Math.max(nums[0], nums[1]);
 
  for (let i = 2; i < nums.length; i++) {
    const curr = Math.max(prev1, prev2 + nums[i]);
    prev2 = prev1;
    prev1 = curr;
  }
 
  return prev1;
}
 
console.log(rob([2, 7, 9, 3, 1])); // 12 (rob houses 0, 2, 4)
# Python - House Robber
def rob(nums: list[int]) -> int:
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
 
    prev2, prev1 = nums[0], max(nums[0], nums[1])
 
    for i in range(2, len(nums)):
        prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
 
    return prev1
 
print(rob([2, 7, 9, 3, 1]))  # 12

Time: O(n). Space: O(1).

Problem 3: Coin Change

Given coins of different denominations and a total amount, find the fewest number of coins needed to make up that amount. Return -1 if impossible.

5-step framework:

  1. State: dp[amount] = minimum coins to make amount
  2. Recurrence: dp[i] = min(dp[i - coin] + 1) for each coin
  3. Base cases: dp[0] = 0
  4. Order: Bottom-up (0 → amount)
  5. Space: O(amount)
// TypeScript - Coin Change
function coinChange(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
 
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i && dp[i - coin] !== Infinity) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
 
  return dp[amount] === Infinity ? -1 : dp[amount];
}
 
console.log(coinChange([1, 5, 10, 25], 30)); // 2 (25 + 5)
console.log(coinChange([2], 3));              // -1
# Python - Coin Change
def coin_change(coins: list[int], amount: int) -> int:
    dp = [float("inf")] * (amount + 1)
    dp[0] = 0
 
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] != float("inf"):
                dp[i] = min(dp[i], dp[i - coin] + 1)
 
    return dp[amount] if dp[amount] != float("inf") else -1
 
print(coin_change([1, 5, 10, 25], 30))  # 2
print(coin_change([2], 3))               # -1

Time: O(amount × coins). Space: O(amount).

Problem 4: Longest Increasing Subsequence (LIS)

Given an integer array, find the length of the longest strictly increasing subsequence.

5-step framework:

  1. State: dp[i] = length of LIS ending at index i
  2. Recurrence: dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]
  3. Base cases: dp[i] = 1 for all i (each element alone is a subsequence)
  4. Order: Bottom-up (0 → n)
  5. Answer: max(dp) — LIS can end at any index
// TypeScript - Longest Increasing Subsequence
// O(n²) DP solution
function lengthOfLIS(nums: number[]): number {
  const n = nums.length;
  const dp = new Array(n).fill(1);
 
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
 
  return Math.max(...dp);
}
 
// O(n log n) binary search optimization
function lengthOfLISOptimal(nums: number[]): number {
  const tails: number[] = []; // smallest tail for each LIS length
 
  for (const num of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = Math.floor((lo + hi) / 2);
      if (tails[mid] < num) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = num;
  }
 
  return tails.length;
}
 
console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4 → [2,3,7,101]
# Python - Longest Increasing Subsequence
# O(n²) DP solution
def length_of_lis(nums: list[int]) -> int:
    n = len(nums)
    dp = [1] * n
 
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
 
    return max(dp)
 
# O(n log n) binary search optimization
import bisect
 
def length_of_lis_optimal(nums: list[int]) -> int:
    tails = []
    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)
 
print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))  # 4

Time: O(n²) basic, O(n log n) optimized. Space: O(n).

3. 2D Dynamic Programming

Problem 5: Unique Paths

A robot starts at the top-left corner of an m × n grid. It can only move right or down. How many unique paths exist to reach the bottom-right corner?

5-step framework:

  1. State: dp[i][j] = number of paths to reach cell (i, j)
  2. Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1] (from above + from left)
  3. Base cases: dp[0][j] = 1, dp[i][0] = 1 (only one way along edges)
  4. Order: Row by row, left to right
  5. Space: O(n) — only need current and previous row → single row suffices
// TypeScript - Unique Paths
function uniquePaths(m: number, n: number): number {
  const dp = new Array(n).fill(1);
 
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[j] += dp[j - 1]; // dp[j] already has value from row above
    }
  }
 
  return dp[n - 1];
}
 
console.log(uniquePaths(3, 7)); // 28
# Python - Unique Paths
def unique_paths(m: int, n: int) -> int:
    dp = [1] * n
 
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]
 
    return dp[n - 1]
 
print(unique_paths(3, 7))  # 28

Time: O(m × n). Space: O(n).

Problem 6: Longest Common Subsequence (LCS)

Given two strings, find the length of their longest common subsequence — the longest sequence of characters that appears in both strings in the same order (not necessarily contiguous).

5-step framework:

  1. State: dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]
  2. Recurrence:
    • 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])
  3. Base cases: dp[0][j] = 0, dp[i][0] = 0
  4. Order: Row by row
  5. Space: O(n) with rolling array
// TypeScript - Longest Common Subsequence
function longestCommonSubsequence(text1: string, text2: string): number {
  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]) {
        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];
}
 
console.log(longestCommonSubsequence("abcde", "ace")); // 3 → "ace"
# Python - Longest Common Subsequence
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]:
                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]
 
print(longest_common_subsequence("abcde", "ace"))  # 3

Time: O(m × n). Space: O(m × n), optimizable to O(n).

Problem 7: Edit Distance

Given two strings word1 and word2, return the minimum number of operations (insert, delete, replace) to convert word1 to word2.

5-step framework:

  1. State: dp[i][j] = min operations to convert word1[0..i-1] to word2[0..j-1]
  2. Recurrence:
    • If word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] (no operation)
    • Else: dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) (replace, delete, insert)
  3. Base cases: dp[i][0] = i (delete all), dp[0][j] = j (insert all)
  4. Order: Row by row
// TypeScript - Edit Distance
function minDistance(word1: string, word2: string): number {
  const m = word1.length, n = word2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
 
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;
 
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j - 1], // replace
          dp[i - 1][j],     // delete
          dp[i][j - 1]      // insert
        );
      }
    }
  }
 
  return dp[m][n];
}
 
console.log(minDistance("horse", "ros"));     // 3
console.log(minDistance("intention", "execution")); // 5
# Python - Edit Distance
def min_distance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    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 word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j - 1],  # replace
                    dp[i - 1][j],      # delete
                    dp[i][j - 1],      # insert
                )
 
    return dp[m][n]
 
print(min_distance("horse", "ros"))      # 3
print(min_distance("intention", "execution"))  # 5

Time: O(m × n). Space: O(m × n).

Problem 8: 0/1 Knapsack

Given n items with weights and values, and a knapsack of capacity W, find the maximum value you can carry without exceeding the weight limit. Each item can be taken at most once.

5-step framework:

  1. State: dp[i][w] = max value using items 0..i-1 with capacity w
  2. Recurrence: dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])
    • Skip item i, or take it (if it fits)
  3. Base cases: dp[0][w] = 0 for all w
  4. Order: Item by item, capacity 0 → W
  5. Space: O(W) with 1D optimization (iterate capacity backwards)
// TypeScript - 0/1 Knapsack
function knapsack(weights: number[], values: number[], capacity: number): number {
  const n = weights.length;
  // Space-optimized 1D DP
  const dp = new Array(capacity + 1).fill(0);
 
  for (let i = 0; i < n; i++) {
    // Iterate backwards to avoid using item i twice
    for (let w = capacity; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
 
  return dp[capacity];
}
 
console.log(knapsack([2, 3, 4, 5], [3, 4, 5, 6], 8)); // 10
# Python - 0/1 Knapsack
def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    n = len(weights)
    dp = [0] * (capacity + 1)
 
    for i in range(n):
        # Iterate backwards to ensure each item used at most once
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
 
    return dp[capacity]
 
print(knapsack([2, 3, 4, 5], [3, 4, 5, 6], 8))  # 10

Time: O(n × W). Space: O(W).

Problem 9: Partition Equal Subset Sum

Given an integer array, determine if it can be partitioned into two subsets with equal sum.

Approach: This is a 0/1 knapsack variant. Target = totalSum / 2. Can we find a subset that sums to target?

// TypeScript - Partition Equal Subset Sum
function canPartition(nums: number[]): boolean {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;
 
  const target = total / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;
 
  for (const num of nums) {
    for (let j = target; j >= num; j--) {
      dp[j] = dp[j] || dp[j - num];
    }
  }
 
  return dp[target];
}
 
console.log(canPartition([1, 5, 11, 5])); // true → [1,5,5] and [11]
console.log(canPartition([1, 2, 3, 5]));  // false
# Python - Partition Equal Subset Sum
def can_partition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0:
        return False
 
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
 
    for num in nums:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
 
    return dp[target]
 
print(can_partition([1, 5, 11, 5]))  # True
print(can_partition([1, 2, 3, 5]))   # False

Time: O(n × target). Space: O(target).

Problem 10: Word Break

Given a string s and a dictionary of words, return true if s can be segmented into dictionary words.

5-step framework:

  1. State: dp[i] = can s[0..i-1] be segmented?
  2. Recurrence: dp[i] = true if there exists j < i where dp[j] is true and s[j..i-1] is in the dictionary
  3. Base case: dp[0] = true (empty string)
// TypeScript - Word Break
function wordBreak(s: string, wordDict: string[]): boolean {
  const words = new Set(wordDict);
  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  dp[0] = true;
 
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && words.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
 
  return dp[n];
}
 
console.log(wordBreak("leetcode", ["leet", "code"]));  // true
console.log(wordBreak("applepenapple", ["apple", "pen"])); // true
# Python - Word Break
def word_break(s: str, word_dict: list[str]) -> bool:
    words = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
 
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
 
    return dp[n]
 
print(word_break("leetcode", ["leet", "code"]))   # True
print(word_break("applepenapple", ["apple", "pen"]))  # True

Time: O(n² × k) where k = average word length. Space: O(n).

4. Common DP Patterns

PatternState DefinitionExamples
Linear (1D)dp[i] = answer for first i elementsClimbing stairs, House Robber, Coin Change
Two-string (2D)dp[i][j] = answer for s1[0..i] and s2[0..j]LCS, Edit Distance
Grid (2D)dp[i][j] = answer for cell (i,j)Unique Paths, Min Path Sum
Knapsackdp[i][w] = answer using items 0..i with capacity w0/1 Knapsack, Subset Sum
Intervaldp[i][j] = answer for range [i..j]Burst Balloons, Matrix Chain
Subsequencedp[i] = answer for subsequence ending at iLIS, Maximum Subarray
State machinedp[i][state] = answer at position i in given stateBest Time to Buy/Sell Stock

Pattern Recognition Tips

  • "Minimum / maximum / count of ways" → likely DP
  • "Can this be done?" (yes/no) → DP with boolean states
  • "Partition into subsets" → Knapsack variant
  • "Subsequence / substring" → 1D or 2D DP
  • "Two strings comparison" → 2D DP (LCS / Edit Distance pattern)
  • "Grid traversal with constraints" → 2D DP

5. Greedy Algorithms

5.1 What Is a Greedy Algorithm?

A greedy algorithm makes the locally optimal choice at each step, hoping to find the global optimum. Unlike DP, it never reconsiders past choices.

5.2 Greedy vs DP

PropertyGreedyDynamic Programming
ApproachLocal optimal → global optimalSolve all subproblems → combine
Reconsiders?NeverCompares all options
Proof needed?Must prove greedy worksOptimal substructure suffices
ComplexityUsually O(n log n) or O(n)Usually O(n²) or O(n × W)
ExampleFractional knapsack0/1 knapsack

Key insight: Greedy is simpler and faster — but only works when you can prove that the locally optimal choice leads to the globally optimal solution. When unsure, use DP.

5.3 When Greedy Works

Greedy works when the problem has:

  1. Greedy choice property: A locally optimal choice leads to a globally optimal solution
  2. Optimal substructure: Optimal solution contains optimal solutions to subproblems

6. Classic Greedy Problems

Problem 11: Jump Game

Given an array where each element represents the maximum jump length from that position, determine if you can reach the last index.

Greedy insight: Track the farthest index reachable. If you can't reach the current index, return false.

// TypeScript - Jump Game
function canJump(nums: number[]): boolean {
  let farthest = 0;
 
  for (let i = 0; i < nums.length; i++) {
    if (i > farthest) return false;
    farthest = Math.max(farthest, i + nums[i]);
  }
 
  return true;
}
 
console.log(canJump([2, 3, 1, 1, 4])); // true
console.log(canJump([3, 2, 1, 0, 4])); // false
# Python - Jump Game
def can_jump(nums: list[int]) -> bool:
    farthest = 0
    for i in range(len(nums)):
        if i > farthest:
            return False
        farthest = max(farthest, i + nums[i])
    return True
 
print(can_jump([2, 3, 1, 1, 4]))  # True
print(can_jump([3, 2, 1, 0, 4]))  # False

Time: O(n). Space: O(1).

Problem 12: Jump Game II

Given the same setup, find the minimum number of jumps to reach the last index.

Greedy insight: Use BFS-like levels. At each "level", find the farthest you can reach. Each level = one jump.

// TypeScript - Jump Game II
function jump(nums: number[]): number {
  let jumps = 0;
  let currentEnd = 0;
  let farthest = 0;
 
  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);
 
    if (i === currentEnd) {
      jumps++;
      currentEnd = farthest;
    }
  }
 
  return jumps;
}
 
console.log(jump([2, 3, 1, 1, 4])); // 2
# Python - Jump Game II
def jump(nums: list[int]) -> int:
    jumps = 0
    current_end = 0
    farthest = 0
 
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest
 
    return jumps
 
print(jump([2, 3, 1, 1, 4]))  # 2

Time: O(n). Space: O(1).

Problem 13: Activity Selection / Non-overlapping Intervals

Given intervals [start, end], find the maximum number of non-overlapping intervals.

Greedy insight: Sort by end time. Always pick the interval that ends earliest — this leaves the most room for future intervals.

// TypeScript - Non-overlapping Intervals (return min removals)
function eraseOverlapIntervals(intervals: number[][]): number {
  intervals.sort((a, b) => a[1] - b[1]); // Sort by end time
 
  let count = 0;
  let prevEnd = -Infinity;
 
  for (const [start, end] of intervals) {
    if (start >= prevEnd) {
      prevEnd = end; // Keep this interval
    } else {
      count++; // Remove this interval (overlaps)
    }
  }
 
  return count;
}
 
console.log(eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]])); // 1
# Python - Non-overlapping Intervals
def erase_overlap_intervals(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[1])  # Sort by end time
    count = 0
    prev_end = float("-inf")
 
    for start, end in intervals:
        if start >= prev_end:
            prev_end = end
        else:
            count += 1
 
    return count
 
print(erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]]))  # 1

Time: O(n log n). Space: O(1).

Problem 14: Gas Station

There are n gas stations in a circle. gas[i] is the gas at station i, cost[i] is the gas needed to travel to station i+1. Find the starting station index for a full loop, or -1 if impossible.

Greedy insight: If total gas ≥ total cost, a solution exists. Start from the station where the running tank first goes negative — the next station is the answer.

// TypeScript - Gas Station
function canCompleteCircuit(gas: number[], cost: number[]): number {
  let totalTank = 0;
  let currentTank = 0;
  let start = 0;
 
  for (let i = 0; i < gas.length; i++) {
    const net = gas[i] - cost[i];
    totalTank += net;
    currentTank += net;
 
    if (currentTank < 0) {
      start = i + 1;
      currentTank = 0;
    }
  }
 
  return totalTank >= 0 ? start : -1;
}
 
console.log(canCompleteCircuit([1,2,3,4,5], [3,4,5,1,2])); // 3
# Python - Gas Station
def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
    total_tank = 0
    current_tank = 0
    start = 0
 
    for i in range(len(gas)):
        net = gas[i] - cost[i]
        total_tank += net
        current_tank += net
 
        if current_tank < 0:
            start = i + 1
            current_tank = 0
 
    return start if total_tank >= 0 else -1
 
print(can_complete_circuit([1,2,3,4,5], [3,4,5,1,2]))  # 3

Time: O(n). Space: O(1).

7. DP vs Greedy Decision Guide

Problem TypeUse GreedyUse DP
Fractional knapsack✅ Take by value/weight ratio—
0/1 knapsack❌ Greedy fails✅
Jump Game (can reach?)✅ Track farthest—
Coin Change (min coins)❌ Greedy fails for arbitrary coins✅
Activity Selection✅ Sort by end time—
Longest Increasing Subsequence—✅
Interval scheduling✅ Sort by end time—
Edit Distance—✅

8. Complexity Reference

DP Problems

ProblemTimeSpaceSpace Optimized
Climbing StairsO(n)O(n)O(1)
House RobberO(n)O(n)O(1)
Coin ChangeO(n × amount)O(amount)—
LISO(n²) / O(n log n)O(n)—
Unique PathsO(m × n)O(m × n)O(n)
LCSO(m × n)O(m × n)O(n)
Edit DistanceO(m × n)O(m × n)O(n)
0/1 KnapsackO(n × W)O(n × W)O(W)
Partition SubsetO(n × sum)O(sum)—
Word BreakO(n²)O(n)—

Greedy Problems

ProblemTimeSpace
Jump GameO(n)O(1)
Jump Game IIO(n)O(1)
Non-overlapping IntervalsO(n log n)O(1)
Gas StationO(n)O(1)

9. Practice Problems

Easy (Build Foundation)

#ProblemPatternApproach
1Climbing Stairs1D DPdp[i] = dp[i-1] + dp[i-2]
2Min Cost Climbing Stairs1D DPdp[i] = cost[i] + min(dp[i-1], dp[i-2])
3Maximum SubarrayKadane's / DPTrack max ending here
4Best Time to Buy and Sell StockGreedyTrack min price, max profit
5Is SubsequenceGreedy / Two pointerMatch characters greedily

Medium (Build Confidence)

#ProblemPatternApproach
6House Robber1D DPmax(skip, rob + dp[i-2])
7Coin ChangeKnapsackmin coins for each amount
8Longest Increasing SubsequenceSubsequence DPdp[i] = max(dp[j]+1) for j < i
9Unique PathsGrid DPdp[i][j] = dp[i-1][j] + dp[i][j-1]
10Longest Common SubsequenceTwo-string DPMatch or max(skip)
11Word Break1D DPdp[i] = any dp[j] && s[j:i] in dict
12Partition Equal Subset SumKnapsackSubset sum = total/2
13Jump GameGreedyTrack farthest reachable
14Jump Game IIGreedy (BFS)Level-by-level jumps
15Non-overlapping IntervalsGreedySort by end, count kept
16Gas StationGreedyTrack tank and start

Hard (Master Level)

#ProblemPatternApproach
17Edit DistanceTwo-string DPinsert/delete/replace min
18Regular Expression MatchingTwo-string DPHandle '.' and '*' cases
19Burst BalloonsInterval DPdp[i][j] = max(burst last)
20Longest Valid Parentheses1D DP / StackTrack valid ranges

Summary

Dynamic Programming and Greedy Algorithms are the two pillars of optimization in computer science — and the final boss of coding interviews.

The DP framework (5 steps):

  1. Define the state
  2. Write the recurrence relation
  3. Identify base cases
  4. Choose computation order (top-down or bottom-up)
  5. Optimize space

Common DP patterns:

  • 1D: Climbing stairs, House Robber, Coin Change, Word Break
  • 2D grid: Unique Paths, Min Path Sum
  • Two-string: LCS, Edit Distance
  • Knapsack: 0/1 Knapsack, Subset Sum, Coin Change

When to use greedy:

  • You can prove local optimal = global optimal
  • Sorting + one pass usually works
  • Examples: Jump Game, Activity Selection, Gas Station

When to use DP:

  • Overlapping subproblems exist
  • You need to consider all possibilities
  • Greedy doesn't work (e.g., 0/1 knapsack, coin change with arbitrary denominations)

This concludes our DSA series! You now have the complete toolkit — from arrays and strings through trees, graphs, heaps, sorting, and now DP and greedy. The key to mastery is practice: pick problems from the tables above, apply the frameworks, and build pattern recognition through repetition.

Previous: Heaps & Priority Queues
Series Overview: Data Structures & Algorithms Roadmap

📬 Subscribe to Newsletter

Get the latest blog posts delivered to your inbox every week. No spam, unsubscribe anytime.

We respect your privacy. Unsubscribe at any time.

💬 Comments

Sign in to leave a comment

We'll never post without your permission.