GATE CS - ALGORITHMS:Dynamic Programming — GATE CS Deep Dive

Dynamic Programming — GATE CS Deep Dive

Dynamic Programming (DP) consistently appears in GATE CS, contributing 4–6 marks. The key is recognising the optimal substructure and overlapping subproblems pattern, then deriving the recurrence before coding.

The DP Framework

Every DP problem follows four steps:

1. Define state: What does dp[i] (or dp[i][j]) represent?
2. Base case: What is the trivial answer for the smallest subproblem?
3. Recurrence: How does dp[i] relate to smaller states?
4. Answer: Where in the DP table is the final answer?

Classic GATE DP Problems

1. 0/1 Knapsack

Problem: n items, each with weight w[i] and value v[i]. Knapsack capacity W. Maximize total value without exceeding W.

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

Recurrence:

• Don't take item i: dp[i][w] = dp[i-1][w]
• Take item i (if w[i] ≤ w): dp[i][w] = dp[i-1][w-w[i]] + v[i]
• dp[i][w] = max of both options

Complexity: O(n × W) time, O(n × W) space (can reduce to O(W)).

Items: weight=[1,3,4,5], value=[1,4,5,7], W=7

dp table (rows=items, cols=capacity 0..7):
        0  1  2  3  4  5  6  7
item 1: 0  1  1  1  1  1  1  1
item 2: 0  1  1  4  5  5  5  5
item 3: 0  1  1  4  5  6  6  9
item 4: 0  1  1  4  5  7  8  9

Answer: dp[4][7] = 9 (items 2+3: value 4+5=9, weight 3+4=7 ✓)

GATE trap: 0/1 means each item used at most once. Fractional knapsack is solvable greedily by value/weight ratio.

2. Longest Common Subsequence (LCS)

Problem: Given strings X (length m) and Y (length n), find the length of their longest common subsequence.

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

Recurrence:

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

Base case: dp[0][j] = dp[i][0] = 0

Example: X = "ABCBDAB", Y = "BDCABA"

     "" B  D  C  A  B  A
""    0  0  0  0  0  0  0
A     0  0  0  0  1  1  1
B     0  1  1  1  1  2  2
C     0  1  1  2  2  2  2
B     0  1  1  2  2  3  3
D     0  1  2  2  2  3  3
A     0  1  2  2  3  3  4
B     0  1  2  2  3  4  4

LCS length = 4 (e.g. "BCBA" or "BCAB")

3. Longest Increasing Subsequence (LIS)

State: dp[i] = length of LIS ending at index i.

Recurrence: dp[i] = 1 + max(dp[j]) for all j < i where A[j] < A[i].

Base case: dp[i] = 1 for all i.

Answer: max(dp[0..n-1]).

Complexity: O(n²) with DP, O(n log n) with patience sorting + binary search.

Array: [10, 9, 2, 5, 3, 7, 101, 18]
dp:    [ 1, 1, 1, 2, 2, 3,  4,  4]
LIS length = 4 (e.g. [2,3,7,18] or [2,5,7,101])

4. Matrix Chain Multiplication

Problem: Given n matrices A₁, A₂, …, Aₙ with dimensions p₀×p₁, p₁×p₂, …, p_{n-1}×pₙ, find the optimal parenthesization to minimize scalar multiplications.

State: dp[i][j] = min cost to multiply matrices Aᵢ through Aⱼ.

Recurrence:

• dp[i][i] = 0
• dp[i][j] = min over k from i to j-1 of: dp[i][k] + dp[k+1][j] + p[i-1] × p[k] × p[j]

Example: Dimensions [30,35,15,5,10,20,25]

Chain length 1: all dp[i][i] = 0
Chain length 2: dp[1][2]=30×35×15=15750, dp[2][3]=35×15×5=2625, ...
Chain length 3: dp[1][3] = min(
    dp[1][1]+dp[2][3]+p[0]×p[1]×p[3] = 0+2625+30×35×5 = 7875,
    dp[1][2]+dp[3][3]+p[0]×p[2]×p[3] = 15750+0+30×15×5 = 18000
) = 7875

5. Coin Change

Two variants that GATE distinguishes:

Minimum coins (optimization): dp[i] = min coins to make amount i.

• dp[0] = 0; dp[i] = 1 + min(dp[i-coin]) for each coin ≤ i
• Complexity: O(amount × num_coins)

Number of ways (counting): dp[i] = number of ways to make amount i.

• Process each coin denomination separately (unbounded knapsack structure)
• Complexity: O(amount × num_coins)

Coins [1, 5, 6, 9], amount = 11

Minimum coins:
dp: [0, 1, 2, 3, 4, 1, 1, 2, 3, 1, 2, 2]
Answer: 2 (5+6=11 or 9+?... wait, min is 2: use 5+6)

Number of ways:
After coin 1: [1,1,1,1,1,1,1,1,1,1,1,1]
After coin 5: [1,1,1,1,1,2,2,2,2,2,3,3]
After coin 6: [1,1,1,1,1,2,3,3,3,3,4,5]
After coin 9: [1,1,1,1,1,2,3,3,3,4,5,6]
Answer: 6 ways

Recurrence Relations and Master Theorem (GATE Favourite)

Master Theorem applies to recurrences of the form T(n) = aT(n/b) + f(n):

• Case 1: f(n) = O(n^{log_b a − ε}) → T(n) = Θ(n^{log_b a})
• Case 2: f(n) = Θ(n^{log_b a}) → T(n) = Θ(n^{log_b a} · log n)
• Case 3: f(n) = Ω(n^{log_b a + ε}) → T(n) = Θ(f(n))

GATE examples:

Substitution method (when Master Theorem doesn't apply): Guess the form of the solution, then prove by induction.

GATE PYQ Patterns

High-frequency topics (from GATE 2015–2025):

1. Complexity class of a given recurrence using Master Theorem
2. LCS of two given strings (fill the DP table)
3. 0/1 Knapsack optimal value
4. Minimum number of coins for a target
5. Count of paths in grid (basic DP counting)
6. Identify if a problem has optimal substructure (justify DP vs greedy)

GATE 2023 style question:

"The recurrence T(n) = T(n/4) + T(3n/4) + n has T(n) = ?"

Answer: Θ(n log n) — solved by Akra-Bazzi or substitution (not directly by Master Theorem).

Practice Problems

1. Solve 0/1 Knapsack for items (w,v): (2,3),(3,4),(4,5),(5,8),(9,10), W=20
2. Find LCS of "AGGTAB" and "GXTXAYB"
3. Compute matrix chain multiplication cost for dimensions [10,30,5,60]
4. Apply Master Theorem: T(n) = 2T(n/4) + n^0.51
5. Prove that Activity Selection Problem (greedy) has optimal substructure