Dynamic Programming for Classic Problems

The Philosophy of Dynamic Programming

Dynamic Programming is an optimization technique that solves complex problems by breaking them into simpler, overlapping subproblems. The solutions to these subproblems are stored (or "memoized") so they don't need to be recomputed. For a problem to be solvable with DP, it must have two key properties.

The following video provides an excellent introduction to DP, contrasting it with the greedy method and defining these essential properties.

The core of solving a DP problem lies in a three-step process:

1. Characterize the structure of an optimal solution.
2. Define the value of the optimal solution recursively (the recurrence relation).
3. Compute the value of the optimal solution, typically in a bottom-up fashion (tabulation).

Let's apply this process to our three classic problems.

Application 1: 0/1 Knapsack Problem

We've mentioned this one already. You have a knapsack of capacity $W$ and n items, each with a weight $w_i$ and a value $v_i$. You must choose a subset of items to put in the knapsack that maximizes total value, without exceeding the capacity. The "0/1" means you either take an item entirely or not at all.

DP Formulation

Let's define our subproblem. The state needs to capture the decision-making process. At any point, we need to know which items are available to us and how much capacity we have left.

• Subproblem State: Let dp[i][w] be the maximum value achievable using a subset of the first i items (from item 1 to item i) with a total knapsack capacity of w.

• Recurrence Relation: To compute dp[i][w], we consider the i-th item. We have two choices:

  1. Don't include item i: In this case, the maximum value is simply the best we could do with the first i-1 items and the same capacity w. The value is dp[i-1][w].
  2. Include item i: This is only possible if the weight of item i (w_i) is less than or equal to the current capacity w. If we include it, we get its value v_i, and the remaining capacity w - w_i must be filled optimally using the first i-1 items. The value is v_i + dp[i-1][w - w_i].

Since we want to maximize the value, we take the best of these two choices.

The renowned instructor Abdul Bari provides a masterclass on this problem. His detailed walkthrough of the tabulation method is essential viewing.

Application 2: Longest Common Subsequence (LCS)

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. The LCS problem is to find the length of the longest subsequence common to two given sequences.

For example, if X = "AGGTAB" and Y = "GXTXAYB", the LCS is "GTAB", and its length is 4.

DP Formulation

• Subproblem State: Let L[i][j] be the length of the LCS of the prefixes X[1...i] and Y[1...j]. Our goal is to find L[m][n] where m and n are the lengths of X and Y, respectively.

• Recurrence Relation: Consider the last characters of the prefixes, X[i] and Y[j].

  1. If X[i] == Y[j]: The characters match! This character must be part of the LCS. The length of the LCS is one plus the length of the LCS of the sequences without these last characters, i.e., X[1...i-1] and Y[1...j-1].
     $L[i][j]=1+L[i-1][j-1]$
  2. If X[i] != Y[j]: The characters do not match. The longest common subsequence must be the longer of two possibilities: the LCS of X[1...i-1] and Y[1...j], or the LCS of X[1...i] and Y[1...j-1]. We essentially discard one of the mismatched characters and find the best outcome.
     $L[i][j]=\max (L[i-1][j],L[i][j-1])$

Let's build the DP table for X = "AGGTAB" and Y = "GXTXAYB" to find the length of the LCS. The table will be of size (m+1) x (n+1). The first row and column are initialized to 0.

The final answer, 4, is in the bottom-right corner.

Application 3: Matrix Chain Multiplication (MCM)

Given a sequence of matrices A_1, A_2, ..., A_n, we want to find the most efficient way to multiply them. The problem is not about performing the multiplications, but merely deciding the order. The cost of multiplying two matrices of dimensions p x q and q x r is p x q x r scalar multiplications.

For example, for matrices A(10x30), B(30x5), C(5x60):

• (AB)C costs (10*30*5) + (10*5*60) = 1500 + 3000 = 4500
• A(BC) costs (30*5*60) + (10*30*60) = 9000 + 18000 = 27000

Clearly, the parenthesization matters a lot.

DP Formulation

• Subproblem State: Let the sequence of matrices be A_i, ..., A_j. The dimensions of matrix A_k are given by p_{k-1} x p_k. Let dp[i][j] be the minimum number of scalar multiplications needed to compute the product A_i...A_j. We want to find dp[1][n].

• Recurrence Relation: To compute the product A_i...A_j, the final multiplication must occur at some split point k (where i \le k < j). That is, we compute (A_i...A_k) * (A_{k+1}...A_j). The cost for a particular split k is the cost of computing the two sub-products plus the cost of multiplying them together.

  • Cost of (A_i...A_k): dp[i][k]
  • Cost of (A_{k+1}...A_j): dp[k+1][j]
  • Cost of final multiplication: p_{i-1} * p_k * p_j

We need to find the split k that minimizes this total cost.

The base cases are dp[i][i] = 0 for all i, as multiplying a single matrix chain has zero cost. The table is filled for increasing chain lengths.

Conclusion

In this lesson, we moved from the shortsightedness of greedy algorithms to the systematic and exhaustive approach of Dynamic Programming. This powerful paradigm guarantees optimality for problems that can be broken down into recurring, overlapping subproblems.

Key Takeaways:

• Dynamic Programming is used for optimization problems that exhibit Optimal Substructure and Overlapping Subproblems.
• The standard DP approach involves defining a state, deriving a recurrence relation, and building a solution table bottom-up (tabulation).
• For 0/1 Knapsack, the recurrence balances the choice of including or excluding an item: dp[i][w] = max(dp[i-1][w], v_i + dp[i-1][w - w_i]).
• For Longest Common Subsequence, the recurrence depends on whether the last characters match: L[i][j] = 1 + L[i-1][j-1] or max(L[i-1][j], L[i][j-1]).
• For Matrix Chain Multiplication, the recurrence finds the optimal split point k for the final multiplication: dp[i][j] = min {dp[i][k] + dp[k+1][j] + ...}.

Mastering the art of formulating these recurrences is key to excelling at DP in the GATE exam.

Having covered two major algorithmic design paradigms, Greedy and Dynamic Programming, we will now turn our attention to fundamental algorithms for the most common data structure in CS: graphs. In the next lesson, we will begin our deep dive into graph algorithms, starting with the essential traversal techniques of Breadth-First Search (BFS) and Depth-First Search (DFS). These traversals form the bedrock for solving a vast array of graph-related problems.