GATE CS - ALGORITHMS:Dynamic Programming for GATE CS

Dynamic Programming for GATE CS

DP on GATE is about defining state + recurrence, then reading a table or complexity — not coding leetcode essays. Typical 4–6 marks when present.

Framework

1. Define $dp[\cdot]$ meaning
2. Base cases
3. Recurrence
4. Where the answer sits

Need optimal substructure and overlapping subproblems. If subproblems do not overlap, plain recursion / D&C may suffice.

Classics

0/1 Knapsack

$dp[i][w] = \max(dp[i-1][w],\, dp[i-1][w-w_i]+v_i)$ if $w_i \le w$.

Time/space $O(nW)$ (space can drop to $O(W)$).

LCS

$dp[i][j]$ = LCS length of prefixes. Match ⇒ diagonal +1; else max(skip). Time $O(mn)$.

Matrix chain / rod cutting / coin change

Same pattern: try last cut / last coin, take min/max. GATE often gives the recurrence and asks complexity or a filled cell.

Greedy vs DP

Activity selection / Huffman: greedy choice property. Knapsack fractional is greedy; 0/1 is DP. If an option claims greedy for 0/1, reject it.

Practice: GATE hub. Graphs next: Graph Algorithms.