GATE/Algorithms/Dynamic Programming
Sign in to track
Hard20 min readAlgorithms

Dynamic Programming

DP solves problems by storing solutions to overlapping subproblems. GATE tests classic DP problems with a focus on recurrences and complexities.

Key Points

  • ·Two properties: optimal substructure + overlapping subproblems
  • ·Top-down (memoisation): recursive + cache; Bottom-up (tabulation): iterative DP table
  • ·LCS: O(mn) time and space
  • ·LIS: O(n²) naive DP; O(n log n) with patience sorting
  • ·0/1 Knapsack: O(nW) pseudo-polynomial
  • ·Matrix Chain Multiplication: O(n³)

What Makes a Problem "DP-able"?

Two conditions must both hold:

1. Optimal Substructure: The optimal solution to the whole problem contains optimal solutions to subproblems.

Example: The shortest path from A to C through B — the A→B portion must also be the shortest path from A to B. (If there were a shorter A→B path, we'd use that instead.)

2. Overlapping Subproblems: The same subproblems are solved multiple times.

Example: Fibonacci — fib(5) calls fib(4) and fib(3). fib(4) also calls fib(3). Without memoisation, fib(3) is computed twice.

Top-Down vs Bottom-Up

Top-Down (Memoisation): Write the natural recursive solution. Add a cache (array/hash map) to remember already-computed answers.

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

Bottom-Up (Tabulation): Fill a table iteratively, starting from the smallest subproblems.

dp[0] = 0, dp[1] = 1
for i from 2 to n:
    dp[i] = dp[i-1] + dp[i-2]

Both give the same answer. Bottom-up avoids recursion stack overflow and is usually faster in practice.

LCS — Longest Common Subsequence

Given strings X = "ABCBDAB" and Y = "BDCAB", find the longest sequence of characters appearing in both (not necessarily contiguous).

LCS = "BCAB" or "BDAB", length = 4.

Recurrence:

dp[i][j] = length of LCS of X[1..i] and Y[1..j]

If X[i] == Y[j]:  dp[i][j] = dp[i-1][j-1] + 1
Else:             dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Filling the table for X="ABC", Y="AC":

dp[i][j]:    "" A  C
          ""  0  0  0
           A  0  1  1
           B  0  1  1
           C  0  1  2   ← LCS length = 2 ("AC")

Time: O(mn), Space: O(mn) or O(min(m,n)) with rolling array.

0/1 Knapsack

You have a knapsack with capacity W. Each item i has weight wᵢ and value vᵢ. You cannot break items. Maximise total value.

Subproblem: dp[i][w] = max value using first i items with capacity w.

If wᵢ > w:    dp[i][w] = dp[i-1][w]            (can't include item i)
Else:         dp[i][w] = max(dp[i-1][w],         (exclude)
                             dp[i-1][w-wᵢ] + vᵢ) (include)

Example: Capacity W=5, items: (w=2,v=3), (w=3,v=4), (w=2,v=2)

dp[0][0..5] = [0,0,0,0,0,0]  (no items → value 0)

Item 1 (w=2,v=3):
dp[1][0]=0, dp[1][1]=0, dp[1][2]=3, dp[1][3]=3, dp[1][4]=3, dp[1][5]=3

Item 2 (w=3,v=4):
dp[2][3]=max(3, 0+4)=4, dp[2][4]=max(3, dp[1][1]+4)=4,
dp[2][5]=max(3, dp[1][2]+4)=max(3,7)=7  ← take both items!

Time: O(nW). Pseudo-polynomial — W can be exponentially large in input bit size.

Matrix Chain Multiplication

Given matrices A₁A₂...Aₙ, find the optimal parenthesisation to minimise scalar multiplications.

Key fact: (A × B) × C has different cost from A × (B × C).

Subproblem: dp[i][j] = minimum cost to multiply matrices i through j.

dp[i][i] = 0  (single matrix, no multiplication)

For chains of length L = 2 to n:
  For each i:
    j = i + L - 1
    dp[i][j] = min over k (i ≤ k < j):
               dp[i][k] + dp[k+1][j] + p[i-1]×p[k]×p[j]

Where p[i-1], p[k], p[j] are dimensions (matrix i has dimensions p[i-1] × p[i]).

Time: O(n³), Space: O(n²).

Edit Distance (Levenshtein)

Minimum number of insert/delete/replace operations to transform string X into Y.

dp[i][j] = edit distance between X[1..i] and Y[1..j]

If X[i] == Y[j]: dp[i][j] = dp[i-1][j-1]       (no cost)
Else:            dp[i][j] = 1 + min(
                               dp[i-1][j],    // delete from X
                               dp[i][j-1],    // insert into X
                               dp[i-1][j-1]   // replace
                             )

Example: X="CAT", Y="CAR"

dp[i][j]:   ""  C  A  R
         ""  0   1  2  3
          C  1   0  1  2
          A  2   1  0  1
          T  3   2  1  1   ← edit distance = 1 (replace T with R)

Quick Check

Q1. LCS of "GATE" and "DATE" — what is its length?

Answer: LCS = "ATE" → length 3.

Q2. 0/1 Knapsack with capacity 4, items (w=1,v=1), (w=3,v=4), (w=4,v=5). What is max value?

Answer: Take items 2 (w=3,v=4) and 1 (w=1,v=1) → weight=4, value=5. Or take item 3 (w=4,v=5) → same weight, same value.

Q3. Why is 0/1 Knapsack called "pseudo-polynomial"?

Answer: O(nW) time looks polynomial, but W can be represented with log W bits — so the algorithm is exponential in the input size (number of bits to represent W).

Key Formulas

  • LCS recurrence: dp[i][j] = dp[i-1][j-1]+1 if match, else max(dp[i-1][j], dp[i][j-1])
  • 0/1 Knapsack: dp[i][w] = max(dp[i-1][w], val[i] + dp[i-1][w-wt[i]])
  • Matrix Chain: dp[i][j] = min_k { dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j] }
  • Edit Distance: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

GATE Exam Tips

  • ★0/1 Knapsack is NP-hard (pseudo-polynomial, not truly polynomial)
  • ★LCS vs Edit Distance: LCS counts common characters; edit distance counts transformation steps
  • ★Matrix Chain: n matrices → n-1 splits to try at each step → O(n³)
  • ★Longest path in DAG: O(V+E) using DP on topological order

Finished reading this topic?

Mark it complete to track your study progress.

Sign in to track