🧠 Dynamic Programming Fundamentals

🎯 What is Dynamic Programming?

Dynamic Programming (DP) is an algorithmic technique that solves complex problems by breaking them down into simpler overlapping subproblems, storing the results of each subproblem to avoid redundant computation. It's built on two key principles:

Optimal Substructure: An optimal solution can be constructed from optimal solutions of its subproblems
Overlapping Subproblems: The same subproblems occur multiple times

📌 Memoization📌 Tabulation📌 State Transition📌 O(n²) to O(n)

The DP Mindset

Core Insight: Instead of recursively solving the same subproblems multiple times, store their results. This transforms exponential time to polynomial time.

Two Approaches:

Top-Down (Memoization) Recursive + caching
Bottom-Up (Tabulation) Iterative + table filling

# The DP Mantra:
# 1. Identify the state (what defines a subproblem)
# 2. Define the recurrence (how subproblems relate)
# 3. Define base cases (smallest subproblems)
# 4. Compute the answer (memoization or tabulation)

# Classic example: Fibonacci
# Without DP: O(2^n) time
# With DP: O(n) time, O(n) space (or O(1) with optimization)

📝 Memoization (Top-Down DP)

🎯 Memoization Technique

Memoization is a top-down approach where we start from the original problem and recursively solve subproblems, caching results in a dictionary or array to avoid recomputation.

Recursive: Natural for many DP problems
Cache: Store results keyed by state parameters
Lazy Evaluation: Only compute what's needed

# Memoization Template
def solve_memo(state, memo):
    # Base case
    if state < base_threshold:
        return base_value
    
    # Check cache
    if state in memo:
        return memo[state]
    
    # Recursive computation
    result = combine(solve_memo(substate1, memo), solve_memo(substate2, memo))
    
    # Store in cache
    memo[state] = result
    return result

# Fibonacci with memoization
def fib_memo(n, memo={}):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

# Time: O(n) | Space: O(n) for cache + O(n) recursion stack

📊 Tabulation (Bottom-Up DP)

🎯 Tabulation Technique

Tabulation is a bottom-up approach where we iteratively fill a table (array) from the smallest subproblems up to the original problem. It avoids recursion overhead.

Iterative: No recursion stack overflow
Table Filling: Systematically compute all subproblems
Space Optimization: Often can reduce to O(1) using rolling arrays

# Tabulation Template
def solve_tab(n):
    # Initialize DP table
    dp = [0] * (n + 1)
    
    # Base cases
    dp[0] = base_value
    dp[1] = base_value
    
    # Fill table iteratively
    for i in range(2, n + 1):
        dp[i] = combine(dp[i-1], dp[i-2], ...)
    
    return dp[n]

# Fibonacci with tabulation
def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# Space-optimized version
def fib_optimized(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    return prev1

# Time: O(n) | Space: O(1) (optimized)

🔢 Fibonacci & Classic DP

🎯 The DP Gateway Problem

Fibonacci sequence is the classic DP problem that illustrates the power of DP. It demonstrates how exponential time (2^n) can be reduced to linear time (O(n)) through memoization or tabulation.

Problem: F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1
Without DP: O(2^n) time, O(n) space
With DP: O(n) time, O(n) or O(1) space

# Comparison of approaches
import time

def fib_recursive(n):
    if n <= 1: return n
    return fib_recursive(n-1) + fib_recursive(n-2)

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

def fib_tab(n):
    if n <= 1: return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# n=40:
# Recursive: ~1 second (millions of calls)
# Memoization: ~0.0001 seconds (40 calls)
# Tabulation: ~0.0001 seconds (40 iterations)

🎒 0/1 Knapsack Problem

🎯 Classic Optimization Problem

Given items with weights and values, choose items to maximize total value within a weight capacity. Each item can be taken at most once (0/1).

State: dp[i][w] = max value using first i items with capacity w
Recurrence: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
Base: dp[0][w] = 0, dp[i][0] = 0

# 0/1 Knapsack with tabulation
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(1, capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], 
                               dp[i-1][w - weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][capacity]

# Space-optimized (1D array)
def knapsack_optimized(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)
    
    for i in range(n):
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]

# Time: O(n * capacity) | Space: O(capacity)

📐 Longest Common Subsequence

🎯 LCS Problem

Find the longest subsequence common to two strings. A subsequence doesn't need to be contiguous but must preserve relative order.

State: dp[i][j] = LCS length of first i chars of s1 and first j chars of s2
Recurrence:
- If s1[i] == s2[j]: dp[i][j] = dp[i-1][j-1] + 1
- Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Base: dp[0][j] = 0, dp[i][0] = 0

# Longest Common Subsequence
def lcs(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])
    
    # Reconstruct LCS
    def reconstruct(i, j):
        if i == 0 or j == 0:
            return ""
        if s1[i-1] == s2[j-1]:
            return reconstruct(i-1, j-1) + s1[i-1]
        elif dp[i-1][j] > dp[i][j-1]:
            return reconstruct(i-1, j)
        else:
            return reconstruct(i, j-1)
    
    return dp[m][n], reconstruct(m, n)

# Time: O(m*n) | Space: O(min(m,n)) with optimization

📈 Longest Increasing Subsequence

🎯 LIS Problem

Find the length of the longest increasing subsequence in an array of numbers. Elements must be in increasing order (strictly).

State: dp[i] = LIS ending at index i
Recurrence: dp[i] = 1 + max(dp[j]) for j < i and nums[j] < nums[i]
Base: dp[i] = 1 (each element is a subsequence of length 1)
Optimization: Patience sorting O(n log n)

# Longest Increasing Subsequence (O(n²))
def lis_length(nums):
    n = len(nums)
    dp = [1] * n
    
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp) if n > 0 else 0

# Optimized O(n log n) using patience sorting
def lis_patience(nums):
    import bisect
    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)

# Time: O(n log n) | Space: O(n)

✏️ Edit Distance (Levenshtein)

🎯 Edit Distance Problem

Find the minimum number of operations (insert, delete, replace) to transform one string into another. Operations have equal cost (or weighted).

State: dp[i][j] = min operations for first i chars of s1 and first j chars of s2
Recurrence:
- If s1[i] == s2[j]: 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])
Base: dp[i][0] = i, dp[0][j] = j

# Edit Distance (Levenshtein)
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],      # delete
                                   dp[i][j-1],      # insert
                                   dp[i-1][j-1])    # replace
    
    return dp[m][n]

# Time: O(m*n) | Space: O(m*n) or O(min(m,n)) optimized

🧮 Matrix Chain Multiplication

🎯 Matrix Chain Problem

Given matrices with dimensions, find the most efficient way to multiply them (minimize the number of scalar multiplications). Parenthesization matters!

State: dp[i][j] = min cost to multiply matrices i through j
Recurrence: dp[i][j] = min(dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j]) for k in [i, j-1]
Base: dp[i][i] = 0 (single matrix)

# Matrix Chain Multiplication
def matrix_chain(dims):
    n = len(dims) - 1  # number of matrices
    dp = [[0] * n for _ in range(n)]
    
    # length = number of matrices in chain
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1]
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[0][n-1]

# Example: dimensions [10, 20, 30, 40, 50]
# Matrices: 10x20, 20x30, 30x40, 40x50
# Optimal parenthesization: (A1(A2(A3A4))) or (A1((A2A3)A4))
# Minimum cost: 38000 multiplications

# Time: O(n³) | Space: O(n²)

⚡ DP Optimization Techniques

🎯 Advanced DP Optimizations

Space Optimization: Rolling arrays (2D → 1D, 1D → O(1))
Divide and Conquer DP: Optimize recurrence with monotonicity
Knuth Optimization: For recurrence dp[i][j] = min(dp[i][k] + dp[k][j]) + C[i][j]
Convex Hull Trick (CHT): For dp[i] = min/max over (m_j * x_i + c_j)
Bitmask DP: For small state spaces using bit operations
Digit DP: For problems involving digits of a number

🎯 Bitmask DP (State Compression)

🎯 Bitmask DP

Bitmask DP is used when the state can be represented as a subset of items. Common in traveling salesman problem (TSP), assignment problems, and subset problems with n ≤ 20.

Mask: Integer where bit i = 1 means item i is included
State: dp[mask] or dp[mask][i] for current position
Transitions: Add one item at a time

# Traveling Salesman Problem (TSP) with bitmask DP
def tsp(dist, n):
    # dp[mask][i] = min cost to visit all nodes in mask, ending at i
    dp = [[float('inf')] * n for _ in range(1 << n)]
    
    # Start from any node (or node 0)
    for i in range(n):
        dp[1 << i][i] = 0
    
    for mask in range(1 << n):
        for last in range(n):
            if not (mask & (1 << last)):
                continue
            for next_node in range(n):
                if mask & (1 << next_node):
                    continue
                new_mask = mask | (1 << next_node)
                dp[new_mask][next_node] = min(
                    dp[new_mask][next_node],
                    dp[mask][last] + dist[last][next_node]
                )
    
    # Return to start (or min over all endpoints)
    return min(dp[(1 << n) - 1][i] + dist[i][0] for i in range(n))

# Time: O(n² * 2^n) | Space: O(n * 2^n)

🔢 Digit DP

🎯 Digit DP

Digit DP is used for problems involving digits of a number, such as counting numbers in [0, X] with certain digit properties (e.g., no consecutive 1s, sum of digits, etc.).

State: dp[pos][state][tight]
pos: Current digit position
tight: Whether we are bound by the limit
state: Any relevant information (e.g., previous digit, sum)

# Count numbers from 0 to X with no consecutive 1s in binary
def count_no_consecutive_ones(x):
    # Convert to binary string
    binary = bin(x)[2:]
    n = len(binary)
    
    from functools import lru_cache
    
    @lru_cache(None)
    def dp(pos, prev_one, tight):
        if pos == n:
            return 1
        
        limit = int(binary[pos]) if tight else 1
        total = 0
        
        for digit in range(limit + 1):
            if prev_one and digit == 1:
                continue
            total += dp(pos + 1, digit == 1, tight and digit == limit)
        
        return total
    
    return dp(0, False, True)

# Example: count numbers <= 5 (101) with no consecutive 1s
# Numbers: 0(0),1(1),2(10),3(11- invalid),4(100),5(101-invalid)
# Result: 4 (0,1,2,4)

# Time: O(n * states * 2) | Space: O(n * states)

🌍 Real-World Applications

Bioinformatics: Sequence alignment (LCS, edit distance)
Natural Language Processing: Word segmentation, spell checking
Operations Research: Resource allocation, scheduling, inventory
Economics: Optimal portfolio selection
Networking: Routing protocols (shortest path DP)
Computer Graphics: Path tracing, animation interpolation
Game Development: State-space search, AI planning

📝 Interview Patterns & Problems

🎯 Key Interview Questions

Classic DP: Fibonacci, factorial, catalan numbers
Sequence DP: LCS, LIS, edit distance, longest palindromic subsequence
Knapsack Family: 0/1, unbounded, multiple knapsack
Grid DP: Unique paths, minimum path sum, maze
String DP: Wildcard matching, regular expression, interleaving
Interval DP: Matrix chain, palindrome partitioning, burst balloons
Tree DP: House robber III, diameter, tree DP
Bitmask DP: TSP, subset sums, matching

# DP Pattern Recognition:
# 1. Counting problems (number of ways)
# 2. Optimization problems (min/max)
# 3. Decision problems (yes/no)

# Common DP Categories:
# - Linear DP (Fibonacci, LIS)
# - 2D DP (LCS, knapsack, edit distance)
# - Interval DP (matrix chain)
# - DP on Trees (diameter, maximum path)
# - DP on Graphs (shortest path, DAG)
# - DP with State Compression (bitmask, digit DP)

# Interview Strategy:
# 1. Start with brute force recursion
# 2. Add memoization
# 3. Convert to tabulation
# 4. Optimize space if possible