Dynamic Programming: DP Tables, Optimal Substructure & Overlapping Subproblems

Core Concepts: What is Dynamic Programming?

1. Definition and Key Properties

Dynamic Programming (DP) is a method for solving complex problems by breaking them into simpler subproblems, storing their solutions, and reusing them to avoid redundant computations. It relies on two critical properties:

• Optimal Substructure: An optimal solution to the problem can be constructed from optimal solutions to its subproblems.
• Overlapping Subproblems: The problem can be broken down into subproblems that are reused multiple times.

2. Memoization vs. Tabulation

Visual Trace: Memoization for Fibonacci

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

---

In the Real World

1. eSewa’s Fraud Detection

   • Idea Used: Edit Distance (Levenshtein Distance) in DP to detect typos in transaction IDs.
   • How: If a user enters eSewa123 instead of eSewa124, the system computes the minimum edits (substitution of 3→4) to flag potential fraud.

2. Ncell’s Call Routing Optimization

   • Idea Used: Shortest Path (Floyd-Warshall) in DP to route calls via the cheapest network towers.
   • How: The DP table stores the minimum cost between every pair of towers, updating routes dynamically as traffic changes.

3. Daraz’s Order Fulfillment

   • Idea Used: 0/1 Knapsack to maximize profit from limited warehouse space.
   • How: For a truck with weight capacity W, Daraz selects items to maximize revenue without exceeding W, using a DP table dp[i][w] = max value for first i items and weight w.

---

Classic DP Problems and Solutions

1. 0/1 Knapsack Problem

Problem: Given weights w[] and values v[] of n items, and a knapsack capacity W, maximize the total value without exceeding W.

DP Table Definition: dp[i][w] = max value achievable with first i items and capacity w.

Algorithm (Tabulation):

def knapsack(W, wt, val, n):
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for w in range(1, W+1):
            if wt[i-1] <= w:
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

Trace for Example: Items: (w=[2,3,4], v=[3,4,5]), W=5

Step 1: Fill dp[1][w] (only item 1)
Step 2: Fill dp[2][w] (items 1+2)
Step 3: Fill dp[3][w] (all items)

Final Table:

       0 1 2 3 4 5
     +-----------
Item0|0 0 0 0 0 0
Item1|0 0 3 3 3 3
Item2|0 0 3 4 4 7
Item3|0 0 3 4 7 8

Optimal Selection: Items 1 and 2 (value=7).

---

2. Edit Distance (Levenshtein Distance)

Problem: Compute the minimum number of operations (insert, delete, replace) to convert string A to B.

DP Table Definition: dp[i][j] = edit distance between A[0..i-1] and B[0..j-1].

Algorithm:

def edit_distance(A, B):
    m, n = len(A), len(B)
    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 A[i-1] == B[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]

Trace for "cat" → "car":

       "" c a r
     +---------
""   |0 1 2 3
c    |1 1 2 3
a    |2 1 1 2
t    |3 2 2 2

Result: 1 (replace t→r).

---

3. Matrix Chain Multiplication

Problem: Parenthesize matrix multiplications to minimize scalar operations. Given matrices A1×n1, A2×n2, ..., An×nk, find the optimal order.

DP Table Definition: dp[i][j] = min cost to multiply A[i..j].

Algorithm:

def matrix_chain_order(p):
    n = len(p)-1
    dp = [[0]*n for _ in range(n)]
    for L in range(2, n+1):  # L = chain length
        for i in range(n-L+1):
            j = i + L - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + p[i]*p[k+1]*p[j+1]
                if cost < dp[i][j]: dp[i][j] = cost
    return dp[0][n-1]

Trace for A(10×30), B(30×5), C(5×60):

Step 1: L=2 (pairs)
Step 2: L=3 (triplets)

Optimal Parenthesization: (A×B)×C (cost=15000) vs. A×(B×C) (cost=45000).

---

Comparison: DP vs. Recursion vs. Greedy

---

Exam Tip

1. For DP Problems:

   • Always define the DP table (dp[i][j] = ...) before coding.
   • Trace small cases (e.g., n=3) to verify your table logic.
   • State the recurrence relation clearly (e.g., dp[i][j] = min(...)).

2. Common Pitfalls:

   • Forgetting to initialize the base cases (e.g., dp[0][j] = j for edit distance).
   • Off-by-one errors in table indices (e.g., dp[i-1][j-1] vs. dp[i][j-1]).
   • Misapplying the greedy approach where DP is needed (e.g., knapsack).

3. Floyd-Warshall Shortcut:

   • For all-pairs shortest paths, always use the DP triple loop:

     for k in range(n):  # intermediate node
         for i in range(n):
             for j in range(n):
                 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
     

---

Visual Summary of DP Steps: