Dynamic Programming Notes & Formulas

1. Definitions and Foundations

In the GATE Computer Science curriculum, Dynamic Programming (DP) is not merely a topic; it is a high-yield strategic tool. Students often struggle because they treat DP as "magic" rather than a formal optimization over plain recursion. For the exam, you must distinguish DP by two non-negotiable properties: Overlapping Subproblems (where naive recursion re-computes the same state multiple times) and Optimal Substructure (where the global optimum is composed of local sub-optima).

Dynamic Programming bridges the gap between exponential-time recursive "brute force" and polynomial-time efficiency. By storing results of subproblems, we ensure that each unique state is solved exactly once.

Recursion vs. Dynamic Programming:

| Feature | Naive Recursion | Dynamic Programming |
| :--- | :--- | :--- |
| Redundant Work | High (Re-computes identical subtrees) | Zero (Table lookup after first compute) |
| Time Complexity | Often Exponential (e.g., $O(2^n)$) | Polynomial (e.g., $O(n^k)$) |
| Logic Style | Divide and Conquer (Independent) | Overlapping Subproblems (Dependent) |
| Methodology | Re-evaluation of states | Memoization or Tabulation |

DP implementations are categorized into Memoization (Top-Down)-which caches results of a recursive function-and Tabulation (Bottom-Up)-which iteratively builds a table from base cases. Mastering these foundations is the prerequisite for the core computational logic that follows.

2. Core Idea: The Efficiency Paradigm

The State is the strategic pivot of any DP solution. In a 2nd-year algorithm course, you might focus on the code; in GATE, you must focus on the State Representation. If you cannot define the variables that uniquely identify a subproblem, you cannot derive the recurrence.

The philosophy of "Store and Reuse" addresses the primary bottleneck in algorithm design: repeated computation. Consider a naive recursion tree for Fibonacci or LCS; the branching factor leads to a massive tree of redundant calls. DP "prunes" this tree by visiting each unique state once. The Transition Relation then acts as the logical bridge, defining how a larger state derives its value from smaller, already-solved states. This shift from "branching" to "structured lookup" is what collapses complexity from $O(2^n)$ to $O(n)$.

3. Key Properties for GATE

Identifying these properties is the first step in solving any 2-mark GATE numerical.

• State Representation: This defines the dimensions of your DP table. In Matrix Chain Multiplication (MCM), dimensions like $10 \times 100 \times 5$ define the state space. For instance, multiplying a $10 \times 100$ and a $100 \times 5$ matrix requires $10 \times 100 \times 5 = 5,000$ scalar multiplications.
• Transition Relations: The mathematical heart. For MCM, this is the split point $k$ that minimizes cost across the range $[i, j]$.
• Base Cases: The stopping condition for recursion and the starting point for tabulation. Without these, your iterative table filling is "blind."
• Time-Space Tradeoff: We explicitly trade auxiliary space (the DP table) for a reduction in time.
• State Compression: A favorite GATE "twist." If a recurrence only depends on the previous row (e.g., in 0/1 Knapsack or LCS), we can use a rolling array to reduce space from $O(n^2)$ to $O(n)$.

4. General DP Problem Solving Framework

To avoid "Wrong Recurrence" traps-a common way students lose 2 marks-always follow this 5-step workflow:

1. Identify States: Variables that define the subproblem.
2. Define Recurrence Relation: The logical transition (The "Step").
3. Decide Base Cases: The "Knowns."
4. Choose Memoization vs. Tabulation: Top-Down vs. Bottom-Up.
5. Optimize Space: Can we use a rolling array?

Pattern Recognition Tips:

• Keywords: Look for "minimum/maximum cost," "longest/shortest," or "number of ways."
• Include/Exclude Logic: For problems like 0/1 Knapsack, the recurrence fragment is often:
  $V[i, w] = \max(V[i-1, w], v_i + V[i-1, w-w_i])$
• Complexity Estimation: A "pro-tip" for the exam-$\text{Total Complexity} = \text{Total States} \times \text{Transition Complexity}$. In LCS, we have $m \times n$ states with $O(1)$ transitions, yielding $O(m \times n)$.

5. Memoization (Top-Down DP)

Memoization is strategically advantageous when the problem doesn't require visiting every possible state in the state space. It keeps the intuitive recursive structure but adds a "Cache Check."

• The Flow: Check Cache $\to$ Compute if absent $\to$ Store $\to$ Return.

Memoization Pseudocode Template:

int memo[MAX_N]; // Initialize with -1


```c
int solve(int n)  {
    if (n <= base_case) return value;
    if (memo[n] != -1) return memo[n];
    // Cache Check
    
    memo[n] = recursive_logic(solve(n-1), solve(n-2));
    // Store
    return memo[n];
}

- **Advantage**: Avoids unnecessary subproblems.
- **Disadvantage**: Recursion stack overflow for deep trees ($n > 10^5$).

### 6. Tabulation (Bottom-Up DP)
Tabulation is usually preferred for GATE because it avoids stack overhead and makes space optimization (rolling arrays) transparent.

**Matrix Chain Multiplication (MCM) Example:**
Consider matrices $M_1(10 \times  20)$, $M_2(20 \times  50)$, $M_3(50 \times  1)$, and $M_4(1 \times  100)$. The "ways to parenthesize" drastically change the scalar multiplication count:
- **Plan A**: $(M_1 M_2)(M_3 M_4) \to  (10 \times  20 \times  50) + (50 \times  1 \times  100) + (10 \times  50 \times  100) = 10,000 + 5,000 + 50,000 = 65,000$.
- **Plan B**: $M_1(M_2(M_3 M_4)) \to  (50 \times  1 \times  100) + (20 \times  50 \times  100) + (10 \times  20 \times  100) = 5,000 + 100,000 + 20,000 = 125,000$.

**Tabulation Pseudocode:**
```javascript
for (int len = 2; len <= n; len++) {
    for (int i = 1; i <= n - len + 1; i++) {
        int j = i + len - 1;
        dp[i][j] = INF;
        for (int k = i; k < j; k++) {
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]);
        }
    }
}

7. Time and Space Complexity Analysis

GATE often tests "Order of Growth" through DP problems.

| Problem | Time Complexity | Space Complexity |
| :--- | :--- | :--- |
| Fibonacci | $O(n)$ | $O(1)$ (Iterative/Rolling) |
| LCS | $O(m \times n)$ | $O(n)$ (Rolling array) |
| MCM | $O(n^3)$ | $O(n^2)$ |
| 0/1 Knapsack | $O(n \times W)$ | $O(W)$ (Rolling array) |

• Rolling Array Technique: If $dp[i][j]$ only depends on $dp[i-1][\dots]$, discard the rest of the table. In 0/1 Knapsack, this reduces $O(nW)$ space to $O(W)$, which is a frequent 2-mark question requirement.

8. DP vs. Other Paradigms

Boundary questions (e.g., "Is Bellman-Ford Greedy?") are exam favorites.

| Paradigm | Subproblem Nature | Selection Strategy |
| :--- | :--- | :--- |
| Dynamic Programming | Overlapping | Explores all options (Global) |
| Greedy | Usually Independent | Local optimal choice (Cannot undo) |
| Divide & Conquer | Independent | Breaks and combines |

• Contrast: Dijkstra (Greedy) fails with negative weights because it assumes a local best is globally best. Bellman-Ford (DP) succeeds by relaxing all edges $|V|-1$ times, essentially exploring all path lengths to ensure global optimality.

9. DP Pattern Recognition

Time management is critical (averaging 2.76 minutes per question). Quickly identifying the pattern saves minutes:

• Sequence Problems: LCS, Longest Increasing Subsequence (LIS).
• Partition Problems: MCM, Rod Cutting (Interval DP).
• Grid Problems: Paths in a matrix.
• Manual Overlap: For small $N$ in numericals, draw a tiny recursion tree. If you see $f(2)$ called twice, stop and use DP logic immediately.

10. Classic DP Problems (GATE Core)

• Fibonacci: Entry-level; focus on $O(1)$ space using two variables.
• MCM: Uses the $i \dots k, k+1 \dots j$ split. Remember: $p_{i-1}p_k p_j$ is the combination cost.
• LCS "Reverse Check": A manual shortcut for the exam. If strings have lengths 8 and 7, max possible length is $\min(8, 7) = 7$.
  • Step 1: Check if a subsequence of length 7 exists.
  • Step 2: If not, check length 6, then 5, then 4.
  • Example: $S_1$: PQRPS $S_2$: QPSP. Max length 4. Check QPSP in $S_1$... Yes! Answer is 4. This is much faster than filling a table.
• 0/1 Knapsack: Choice-based recursion ($O(nW)$).
• Bellman-Ford: Relax $d[v] > d[u] + w(u, v)$ for $|V|-1$ passes.

11. Advanced DP & GATE Nuances

• Bitmask DP: Used for subsets (e.g., TSP). State is (mask, last_node).
• DP on Trees: Dependency is parent-child (e.g., Maximum Independent Set on Trees).
• Interval DP: Like MCM, where we solve for ranges $[i, j]$.

12. Common GATE PYQ Patterns and Traps

• Negative Weight Cycle Trap: Bellman-Ford performs $|V|-1$ relaxations. A 10th check (the $n$-th check) is what detects the cycle. If $d[v]$ can still be reduced, a negative cycle exists.
• Distinct Weight MST: If all edges have distinct weights, the MST is unique. This is a property often contrasted with DP pathfinding.
• Recurrence Analysis: Don't confuse DP with D&C. Best-case QuickSort is $O(n \log n)$ via traditional recurrence, while 0/1 Knapsack is $O(nW)$ via DP.

13. Fast Revision Notes (The DP Cheat Sheet)

• Most Repeated Recurrences:
  • LCS: If $S_1[i] == S_2[j]$: $1 + dp[i-1][j-1]$; Else: $\max(dp[i-1][j], dp[i][j-1])$.
  • Knapsack: $\max(V[i-1][w], val[i] + V[i-1][w-wt[i]])$.
  • MCM: $M[i,j] = \min_{i \le k < j} \{M[i,k] + M[k+1,j] + p_{i-1}p_kp_j\}$.
• Complexity Quick-Look:
  • Time: $(\text{Total Unique States}) \times (\text{Time per Transition})$.
  • Space: Check if the recurrence only looks at $dp[i-1]$; if so, optimize to $O(n)$.
• Pro-Tips for the Exam:
  • Space optimization: If the question asks for "Minimum Space," check if the problem can be solved with a 1D array (rolling array).
  • Reverse Check for LCS: When string lengths are small (e.g., $<10$), work backwards from the maximum possible length to bypass table construction.
  • Bellman-Ford: Remember that it is a Dynamic Programming algorithm. Dijkstra is Greedy.
  • Final Strategic Note: Success in DP comes from identifying the State and the Transition. Master these, and you transform the most feared 2-mark questions into guaranteed marks. Keep practicing!