Dynamic Programming

What is Dynamic Programming?

Core Concept

Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them down into simpler subproblems and storing the results to avoid redundant calculations.

📝 Real-Life Analogy:

Think of doing homework problems. Instead of solving the same math problem multiple times, you write down the answer once and refer back to it whenever you need it again.

🎯 When to Use DP:

Optimal Substructure: Problem can be broken into smaller subproblems
Overlapping Subproblems: Same subproblems are solved multiple times
Optimization: Finding minimum, maximum, or counting solutions

Memoization (Top-Down)

Fibonacci with Memoization

Memoization stores the results of expensive function calls and returns the cached result when the same inputs occur again.

🔄 Memoization vs Naive Recursion:

Naive Fibonacci(5) - Exponential Time O(2^n):

                    fib(5)
                   /      \
               fib(4)      fib(3)
              /     \     /     \
          fib(3)  fib(2) fib(2) fib(1)
         /    \   /   \  /   \
     fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
     /   \
  fib(1) fib(0)

❌ Problem: fib(3) calculated 2 times, fib(2) calculated 3 times!

Memoized Fibonacci(5) - Linear Time O(n):

    fib(5) → memo[5] = fib(4) + fib(3)
    fib(4) → memo[4] = fib(3) + fib(2)  
    fib(3) → memo[3] = fib(2) + fib(1)  ← Calculated once, stored
    fib(2) → memo[2] = fib(1) + fib(0)  ← Calculated once, stored
    fib(1) → memo[1] = 1
    fib(0) → memo[0] = 0

✅ Each subproblem calculated exactly once!

Memo Table: [0, 1, 1, 2, 3, 5]
            fib(0) through fib(5)

🌍 Real-World Applications:

💰 Financial Trading: Caching complex option pricing calculations to avoid recalculating the same scenarios

🎮 Game Development: Storing pathfinding results for NPCs to avoid recalculating routes in similar game states

🔍 Web Search: Caching search results and ranking calculations for frequently queried terms

🧬 Bioinformatics: Storing DNA sequence alignment scores to speed up genetic analysis

TypeScript

// Without memoization - O(2^n) time complexity
function fibonacciNaive(n: number): number {
    if (n <= 1) return n;
    return fibonacciNaive(n - 1) + fibonacciNaive(n - 2);
}

// With memoization - O(n) time complexity
function fibonacciMemo(n: number, memo: Map = new Map()): number {
    if (n <= 1) return n;
    
    if (memo.has(n)) {
        return memo.get(n)!;
    }
    
    const result = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
    memo.set(n, result);
    return result;
}

// Alternative using object cache
function fibonacciMemoObj(n: number, cache: {[key: number]: number} = {}): number {
    if (n <= 1) return n;
    
    if (cache[n] !== undefined) {
        return cache[n];
    }
    
    cache[n] = fibonacciMemoObj(n - 1, cache) + fibonacciMemoObj(n - 2, cache);
    return cache[n];
}

// Example usage
console.log(fibonacciMemo(40)); // Much faster than naive approach

Python

# Without memoization - O(2^n) time complexity
def fibonacci_naive(n):
    if n <= 1:
        return n
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)

# With memoization using dictionary
def fibonacci_memo(n, memo=None):
    if memo is None:
        memo = {}
    
    if n <= 1:
        return n
    
    if n in memo:
        return memo[n]
    
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

# Using Python's built-in lru_cache decorator
from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_lru(n):
    if n <= 1:
        return n
    return fibonacci_lru(n - 1) + fibonacci_lru(n - 2)

# Example usage
print(fibonacci_memo(40))  # Much faster than naive approach
print(fibonacci_lru(40))   # Even cleaner with decorator

OCaml

(* Without memoization - O(2^n) time complexity *)
let rec fibonacci_naive n =
  if n <= 1 then n
  else fibonacci_naive (n - 1) + fibonacci_naive (n - 2)

(* With memoization using hashtable *)
let fibonacci_memo n =
  let memo = Hashtbl.create 100 in
  let rec fib n =
    if n <= 1 then n
    else
      try Hashtbl.find memo n
      with Not_found ->
        let result = fib (n - 1) + fib (n - 2) in
        Hashtbl.add memo n result;
        result
  in
  fib n

(* Alternative using Map for immutable memoization *)
module IntMap = Map.Make(Int)

let fibonacci_map n =
  let rec fib n memo =
    if n <= 1 then (n, memo)
    else
      try (IntMap.find n memo, memo)
      with Not_found ->
        let (result1, memo1) = fib (n - 1) memo in
        let (result2, memo2) = fib (n - 2) memo1 in
        let result = result1 + result2 in
        let new_memo = IntMap.add n result memo2 in
        (result, new_memo)
  in
  fst (fib n IntMap.empty)

(* Example usage *)
let result = fibonacci_memo 40 (* Much faster than naive approach *)

🎯 Memoization Benefits:

Easy to implement: Add caching to existing recursive solution
Natural recursion: Maintains recursive structure
Lazy evaluation: Only computes needed subproblems
Space efficient: Only stores computed results

Tabulation (Bottom-Up)

Fibonacci with Tabulation

Tabulation builds up solutions from the smallest subproblems to the target problem, typically using iteration and arrays.

TypeScript

// Tabulation approach - O(n) time, O(n) space
function fibonacciTab(n: number): number {
    if (n <= 1) return n;
    
    const dp: number[] = new Array(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

// Space-optimized version - O(n) time, O(1) space
function fibonacciOptimized(n: number): number {
    if (n <= 1) return n;
    
    let prev2 = 0;
    let prev1 = 1;
    
    for (let i = 2; i <= n; i++) {
        const current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}

// Example: Climbing Stairs Problem
function climbStairs(n: number): number {
    if (n <= 2) return n;
    
    const dp: number[] = new Array(n + 1);
    dp[1] = 1;
    dp[2] = 2;
    
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

console.log(fibonacciTab(10)); // 55
console.log(climbStairs(5)); // 8 ways to climb 5 stairs

Python

# Tabulation approach - O(n) time, O(n) space
def fibonacci_tab(n):
    if n <= 1:
        return n
    
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[n]

# Space-optimized version - O(n) time, O(1) space
def fibonacci_optimized(n):
    if n <= 1:
        return n
    
    prev2, prev1 = 0, 1
    
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    
    return prev1

# Example: Climbing Stairs Problem
def climb_stairs(n):
    if n <= 2:
        return n
    
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[n]

# Example: House Robber Problem
def rob_houses(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    
    for i in range(2, len(nums)):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
    
    return dp[-1]

print(fibonacci_tab(10))  # 55
print(climb_stairs(5))    # 8 ways to climb 5 stairs
print(rob_houses([2, 7, 9, 3, 1]))  # 12 (rob houses 0, 2, 4)

OCaml

(* Tabulation approach - O(n) time, O(n) space *)
let fibonacci_tab n =
  if n <= 1 then n
  else
    let dp = Array.make (n + 1) 0 in
    dp.(0) <- 0;
    dp.(1) <- 1;
    for i = 2 to n do
      dp.(i) <- dp.(i - 1) + dp.(i - 2)
    done;
    dp.(n)

(* Space-optimized version - O(n) time, O(1) space *)
let fibonacci_optimized n =
  if n <= 1 then n
  else
    let prev2 = ref 0 in
    let prev1 = ref 1 in
    for i = 2 to n do
      let current = !prev1 + !prev2 in
      prev2 := !prev1;
      prev1 := current
    done;
    !prev1

(* Example: Climbing Stairs Problem *)
let climb_stairs n =
  if n <= 2 then n
  else
    let dp = Array.make (n + 1) 0 in
    dp.(1) <- 1;
    dp.(2) <- 2;
    for i = 3 to n do
      dp.(i) <- dp.(i - 1) + dp.(i - 2)
    done;
    dp.(n)

(* Example: House Robber Problem *)
let rob_houses nums =
  let len = Array.length nums in
  if len = 0 then 0
  else if len = 1 then nums.(0)
  else
    let dp = Array.make len 0 in
    dp.(0) <- nums.(0);
    dp.(1) <- max nums.(0) nums.(1);
    for i = 2 to len - 1 do
      dp.(i) <- max dp.(i - 1) (dp.(i - 2) + nums.(i))
    done;
    dp.(len - 1)

(* Example usage *)
let result1 = fibonacci_tab 10 (* 55 *)
let result2 = climb_stairs 5   (* 8 ways to climb 5 stairs *)
let result3 = rob_houses [|2; 7; 9; 3; 1|] (* 12 *)

🎯 Tabulation Benefits:

No recursion overhead: Uses iteration instead
Predictable space: Clear memory usage pattern
Bottom-up approach: Builds from base cases
Often more efficient: Better cache locality

Classic DP Problems

0/1 Knapsack Problem

Given items with weights and values, and a knapsack with limited capacity, find the maximum value that can be obtained.

🎒 Real-Life Analogy:

You're packing for a trip with a weight limit. Each item has a value to you and a weight. You want to maximize value while staying under the weight limit.

📊 DP Table Filling Process:

Items: [weight, value]
Item 1: [1, 1]  Item 2: [3, 4]  Item 3: [4, 5]  Item 4: [5, 7]
Capacity: 7

DP Table: dp[i][w] = max value using first i items with capacity w

     w→  0  1  2  3  4  5  6  7
i=0      0  0  0  0  0  0  0  0  ← No items
i=1      0  1  1  1  1  1  1  1  ← Item 1 (w=1, v=1)
i=2      0  1  1  4  5  5  5  5  ← Item 2 (w=3, v=4)
i=3      0  1  1  4  5  6  6  9  ← Item 3 (w=4, v=5)
i=4      0  1  1  4  5  7  8  9  ← Item 4 (w=5, v=7)
         ↑                    ↑
      Base case           Answer: 9

Step-by-step for dp[2][4] (Items 1,2 with capacity 4):
• Don't take Item 2: dp[1][4] = 1
• Take Item 2: dp[1][4-3] + 4 = dp[1][1] + 4 = 1 + 4 = 5
• dp[2][4] = max(1, 5) = 5 ✅

Optimal solution: Items 2 and 3 (values 4+5=9, weights 3+4=7)

🌍 Real-World Applications:

💼 Resource Allocation: Optimizing budget allocation across projects with limited resources

📦 Cargo Loading: Maximizing value of goods in shipping containers with weight constraints

💾 Memory Management: Selecting which processes to keep in limited RAM for optimal performance

🎯 Portfolio Optimization: Selecting investments to maximize returns within risk constraints

⚡ Performance Comparison:

Approach	Time Complexity	Space Complexity	Best For
Brute Force	O(2^n)	O(n)	❌ Never practical
2D DP Table	O(n × W)	O(n × W)	✅ Learning & tracing
1D DP Array	O(n × W)	O(W)	✅ Production use
Memoization	O(n × W)	O(n × W)	⚠️ Recursive overhead

TypeScript

function knapsack(weights: number[], values: number[], capacity: number): number {
    const n = weights.length;
    // dp[i][w] = maximum value using first i items with capacity w
    const dp: number[][] = Array(n + 1).fill(null).map(() => Array(capacity + 1).fill(0));
    
    for (let i = 1; i <= n; i++) {
        for (let w = 1; w <= capacity; w++) {
            // Don't take item i-1
            dp[i][w] = dp[i - 1][w];
            
            // Take item i-1 if it fits
            if (weights[i - 1] <= w) {
                const takeItem = dp[i - 1][w - weights[i - 1]] + values[i - 1];
                dp[i][w] = Math.max(dp[i][w], takeItem);
            }
        }
    }
    
    return dp[n][capacity];
}

// Space-optimized version using 1D array
function knapsackOptimized(weights: number[], values: number[], capacity: number): number {
    const dp: number[] = new Array(capacity + 1).fill(0);
    
    for (let i = 0; i < weights.length; i++) {
        // Traverse backwards to avoid using updated values
        for (let w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    
    return dp[capacity];
}

// Example usage
const weights = [1, 3, 4, 5];
const values = [1, 4, 5, 7];
const capacity = 7;
console.log(knapsack(weights, values, capacity)); // 9

Python

def knapsack(weights, values, capacity):
    n = len(weights)
    # dp[i][w] = maximum value using first i items with capacity w
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            # Don't take item i-1
            dp[i][w] = dp[i - 1][w]
            
            # Take item i-1 if it fits
            if weights[i - 1] <= w:
                take_item = dp[i - 1][w - weights[i - 1]] + values[i - 1]
                dp[i][w] = max(dp[i][w], take_item)
    
    return dp[n][capacity]

# Space-optimized version using 1D array
def knapsack_optimized(weights, values, capacity):
    dp = [0] * (capacity + 1)
    
    for i in range(len(weights)):
        # Traverse backwards to avoid using updated values
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]

# Longest Common Subsequence
def lcs(text1, text2):
    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]

# Example usage
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
print(knapsack(weights, values, capacity))  # 9

print(lcs("abcde", "ace"))  # 3 (longest common subsequence is "ace")

OCaml

(* 0/1 Knapsack Problem *)
let knapsack weights values capacity =
  let n = Array.length weights in
  let dp = Array.make_matrix (n + 1) (capacity + 1) 0 in
  
  for i = 1 to n do
    for w = 1 to capacity do
      (* Don't take item i-1 *)
      dp.(i).(w) <- dp.(i - 1).(w);
      
      (* Take item i-1 if it fits *)
      if weights.(i - 1) <= w then
        let take_item = dp.(i - 1).(w - weights.(i - 1)) + values.(i - 1) in
        dp.(i).(w) <- max dp.(i).(w) take_item
    done
  done;
  
  dp.(n).(capacity)

(* Space-optimized version *)
let knapsack_optimized weights values capacity =
  let dp = Array.make (capacity + 1) 0 in
  
  for i = 0 to Array.length weights - 1 do
    (* Traverse backwards to avoid using updated values *)
    for w = capacity downto weights.(i) do
      dp.(w) <- max dp.(w) (dp.(w - weights.(i)) + values.(i))
    done
  done;
  
  dp.(capacity)

(* Longest Common Subsequence *)
let lcs text1 text2 =
  let m = String.length text1 in
  let n = String.length text2 in
  let dp = Array.make_matrix (m + 1) (n + 1) 0 in
  
  for i = 1 to m do
    for j = 1 to n do
      if text1.[i - 1] = text2.[j - 1] then
        dp.(i).(j) <- dp.(i - 1).(j - 1) + 1
      else
        dp.(i).(j) <- max dp.(i - 1).(j) dp.(i).(j - 1)
    done
  done;
  
  dp.(m).(n)

(* Example usage *)
let weights = [|1; 3; 4; 5|]
let values = [|1; 4; 5; 7|]
let capacity = 7
let result1 = knapsack weights values capacity (* 9 *)

let result2 = lcs "abcde" "ace" (* 3 *)

🎯 Common DP Problem Patterns:

Linear DP: Fibonacci, climbing stairs, house robber
Grid DP: Unique paths, minimum path sum
String DP: Longest common subsequence, edit distance
Knapsack DP: 0/1 knapsack, coin change, subset sum

Problem Type	Time Complexity	Space Complexity
1D DP (Fibonacci)	O(n)	O(n) → O(1)
2D DP (Knapsack)	O(n × W)	O(n × W) → O(W)
String DP (LCS)	O(m × n)	O(m × n) → O(min(m,n))

DSA Interview Guide

Dynamic Programming

🎯 When to Use DP:

🎯 Memoization Benefits:

🎯 Tabulation Benefits:

🎯 Common DP Problem Patterns: