6 - Dynamic Programming

Dynamic Programming (DP) is a powerful algorithmic technique used to solve complex problems by breaking them down into simpler subproblems. It's particularly effective when a problem has overlapping subproblems and optimal substructure.

Understanding Dynamic Programming

What is Dynamic Programming?

Dynamic Programming is a method for solving complex problems by breaking them down into simpler subproblems and storing the results to avoid redundant calculations. The name "dynamic programming" was chosen for political reasons and doesn't have a clear technical meaning - it was designed to sound impressive!

Real-World Analogy

Think of planning a road trip with multiple possible routes. Instead of recalculating the time for common segments every time, you:

• Calculate the time for each road segment once
• Write down these results
• Reuse them when evaluating different routes that share segments

This is exactly what dynamic programming does - it solves each subproblem once and stores the solution for future use.

Key Concepts

Overlapping Subproblems

A problem has overlapping subproblems when the same subproblems need to be solved multiple times.

Example: In calculating the Fibonacci sequence, F(5) requires calculating F(4) and F(3). But F(4) also requires F(3). Without dynamic programming, F(3) would be calculated twice.

F(5)
├── F(4)
│   ├── F(3) ← Calculated twice!
│   │   ├── F(2)
│   │   └── F(1)
│   └── F(2)
└── F(3)
    ├── F(2)
    └── F(1)

Dynamic programming addresses this by solving each subproblem only once and storing the results for future use.

Optimal Substructure

A problem has optimal substructure when the optimal solution to the problem contains optimal solutions to its subproblems.

Example: In the shortest path problem, if the shortest path from A to C goes through B, then the path from A to B and the path from B to C must also be the shortest paths between those points.

This property allows us to build the solution to the original problem from the solutions to its subproblems.

Approaches to Dynamic Programming

There are two main approaches to implementing dynamic programming:

1. Top-Down Approach (Memoization)

The top-down approach starts with the original problem and recursively breaks it down into subproblems. To avoid redundant calculations, it stores the results of subproblems in a cache (usually a dictionary or array).

Example: Fibonacci Sequence with Memoization

/// <summary>
/// Calculates the nth Fibonacci number using memoization.
/// </summary>
/// <param name="n">The position in the Fibonacci sequence.</param>
/// <returns>The nth Fibonacci number.</returns>
public int Fibonacci(int n)
{
    // Create a dictionary to store previously calculated Fibonacci numbers
    return FibonacciMemoized(n, new Dictionary<int, int>());
}

/// <summary>
/// Helper method that implements the memoized Fibonacci calculation.
/// </summary>
/// <param name="n">The position in the Fibonacci sequence.</param>
/// <param name="memo">Dictionary to store previously calculated values.</param>
/// <returns>The nth Fibonacci number.</returns>
private int FibonacciMemoized(int n, Dictionary<int, int> memo)
{
    // Base cases: F(0) = 0, F(1) = 1
    if (n <= 1)
        return n;
    
    // If we've already calculated this value, return it from the cache
    if (memo.ContainsKey(n))
        return memo[n];
    
    // Calculate F(n) = F(n-1) + F(n-2) and store in the cache
    memo[n] = FibonacciMemoized(n - 1, memo) + FibonacciMemoized(n - 2, memo);
    return memo[n];
}

Step-by-Step Explanation

Let's trace through calculating F(5) using memoization:

1. Call Fibonacci(5), which calls FibonacciMemoized(5, {})
2. Since 5 > 1 and 5 is not in the memo, calculate FibonacciMemoized(4, {}) + FibonacciMemoized(3, {})
3. For FibonacciMemoized(4, {}):
   • Calculate FibonacciMemoized(3, {}) + FibonacciMemoized(2, {})
   • For FibonacciMemoized(3, {}):
     • Calculate FibonacciMemoized(2, {}) + FibonacciMemoized(1, {})
     • For FibonacciMemoized(2, {}):
       • Calculate FibonacciMemoized(1, {}) + FibonacciMemoized(0, {}) = 1 + 0 = 1
     • Store memo[2] = 1
     • FibonacciMemoized(1, {}) returns 1 (base case)
     • Store memo[3] = 1 + 1 = 2
   • For FibonacciMemoized(2, {}):
     • Return 1 from memo (already calculated)
   • Store memo[4] = 2 + 1 = 3
4. For FibonacciMemoized(3, {}):
   • Return 2 from memo (already calculated)
5. Store memo[5] = 3 + 2 = 5
6. Return 5

Notice how FibonacciMemoized(2, {}) and FibonacciMemoized(3, {}) are only calculated once, despite being needed multiple times.

2. Bottom-Up Approach (Tabulation)

The bottom-up approach starts with the smallest subproblems and iteratively builds up to the original problem. It typically uses an array or table to store the results of subproblems.

Example: Fibonacci Sequence with Tabulation

/// <summary>
/// Calculates the nth Fibonacci number using tabulation.
/// </summary>
/// <param name="n">The position in the Fibonacci sequence.</param>
/// <returns>The nth Fibonacci number.</returns>
public int Fibonacci(int n)
{
    // Handle base cases
    if (n <= 1)
        return n;
    
    // Create an array to store all Fibonacci numbers from 0 to n
    int[] fib = new int[n + 1];
    fib[0] = 0; // F(0) = 0
    fib[1] = 1; // F(1) = 1
    
    // Build up the array by calculating each Fibonacci number
    for (int i = 2; i <= n; i++)
    {
        // Each number is the sum of the two previous numbers
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    
    // Return the nth Fibonacci number
    return fib[n];
}

Step-by-Step Explanation

Let's trace through calculating F(5) using tabulation:

1. Initialize fib[0] = 0 and fib[1] = 1
2. For i = 2: fib[2] = fib[1] + fib[0] = 1 + 0 = 1
3. For i = 3: fib[3] = fib[2] + fib[1] = 1 + 1 = 2
4. For i = 4: fib[4] = fib[3] + fib[2] = 2 + 1 = 3
5. For i = 5: fib[5] = fib[4] + fib[3] = 3 + 2 = 5
6. Return fib[5] = 5

The bottom-up approach calculates all Fibonacci numbers from 0 to n in order, without recursion.

Comparison of Approaches

Aspect	Top-Down (Memoization)	Bottom-Up (Tabulation)
Implementation	Usually recursive	Usually iterative
Subproblem Solving	Solves only necessary subproblems	Solves all subproblems
Space Efficiency	Can be more space-efficient if not all subproblems are needed	Uses space for all subproblems
Stack Overflow	Potential issue for deep recursion	Not an issue (iterative)
Code Complexity	Often more intuitive and closer to the problem definition	Sometimes more complex to formulate
When to Use	When not all subproblems need to be solved	When most subproblems need to be solved anyway

Classic Dynamic Programming Problems

1. Longest Common Subsequence (LCS)

The LCS problem finds the longest subsequence common to two sequences. 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.

/// <summary>
/// Finds the length of the longest common subsequence of two strings.
/// </summary>
/// <param name="text1">First string.</param>
/// <param name="text2">Second string.</param>
/// <returns>The length of the longest common subsequence.</returns>
public int LongestCommonSubsequence(string text1, string text2)
{
    int m = text1.Length;
    int n = text2.Length;
    
    // Create a 2D array to store LCS lengths
    // dp[i,j] represents the length of LCS of text1[0...i-1] and text2[0...j-1]
    int[,] dp = new int[m + 1, n + 1];
    
    // Fill the dp table
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            // If current characters match, extend the LCS
            if (text1[i - 1] == text2[j - 1])
            {
                dp[i, j] = dp[i - 1, j - 1] + 1;
            }
            else
            {
                // If characters don't match, take the maximum LCS
                // either excluding the current character from text1
                // or excluding the current character from text2
                dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
            }
        }
    }
    
    // The bottom-right cell contains the length of the LCS
    return dp[m, n];
}

Step-by-Step Explanation

Let's trace through finding the LCS of "ABCDE" and "ACE":

1. Initialize a dp table of size (6×4) with zeros:

      | "" | A | C | E
   ---|---|---|---|---
   "" | 0  | 0 | 0 | 0
   A  | 0  |   |   |
   B  | 0  |   |   |
   C  | 0  |   |   |
   D  | 0  |   |   |
   E  | 0  |   |   |

2. Fill the table:

   • For i=1, j=1: text1[0] = 'A', text2[0] = 'A', they match, so dp[1,1] = dp[0,0] + 1 = 1
   • For i=1, j=2: text1[0] = 'A', text2[1] = 'C', they don't match, so dp[1,2] = max(dp[0,2], dp[1,1]) = max(0, 1) = 1
   • Continue filling...

3. Final dp table:

      | "" | A | C | E
   ---|---|---|---|---
   "" | 0  | 0 | 0 | 0
   A  | 0  | 1 | 1 | 1
   B  | 0  | 1 | 1 | 1
   C  | 0  | 1 | 2 | 2
   D  | 0  | 1 | 2 | 2
   E  | 0  | 1 | 2 | 3

4. The LCS length is dp[5,3] = 3, which corresponds to the subsequence "ACE".

2. Knapsack Problem

The 0/1 Knapsack problem involves selecting items with given weights and values to maximize the total value while keeping the total weight under a given limit.

/// <summary>
/// Solves the 0/1 Knapsack problem.
/// </summary>
/// <param name="weights">Array of item weights.</param>
/// <param name="values">Array of item values.</param>
/// <param name="capacity">Maximum weight capacity of the knapsack.</param>
/// <returns>The maximum value that can be obtained.</returns>
public int Knapsack(int[] weights, int[] values, int capacity)
{
    int n = weights.Length;
    
    // Create a 2D array to store maximum values
    // dp[i,w] represents the maximum value that can be obtained
    // using the first i items and with a knapsack capacity of w
    int[,] dp = new int[n + 1, capacity + 1];
    
    // Fill the dp table
    for (int i = 1; i <= n; i++)
    {
        for (int w = 0; w <= capacity; w++)
        {
            // If the current item can fit in the knapsack
            if (weights[i - 1] <= w)
            {
                // Choose the maximum of:
                // 1. Including the current item: value of the item + maximum value
                //    with remaining capacity after including the item
                // 2. Excluding the current item: maximum value without the item
                dp[i, w] = Math.Max(
                    values[i - 1] + dp[i - 1, w - weights[i - 1]], // Include the item
                    dp[i - 1, w] // Exclude the item
                );
            }
            else
            {
                // If the current item doesn't fit, exclude it
                dp[i, w] = dp[i - 1, w];
            }
        }
    }
    
    // The bottom-right cell contains the maximum value
    return dp[n, capacity];
}

Step-by-Step Explanation

Let's trace through solving the Knapsack problem with:

• weights = [2, 3, 4, 5]
• values = [3, 4, 5, 6]
• capacity = 8

1. Initialize a dp table of size (5×9) with zeros

2. Fill the table:

   • For i=1, w=0 to 8:
     • If w < 2: dp[1,w] = dp[0,w] = 0 (can't include the first item)
     • If w ≥ 2: dp[1,w] = max(3 + dp[0,w-2], dp[0,w]) = max(3, 0) = 3
   • Continue filling...

3. Final dp table:

      | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
   ---|---|---|---|---|---|---|---|---|---
   0  | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
   1  | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | 3
   2  | 0 | 0 | 3 | 4 | 4 | 7 | 7 | 7 | 7
   3  | 0 | 0 | 3 | 4 | 5 | 7 | 8 | 9 | 9
   4  | 0 | 0 | 3 | 4 | 5 | 7 | 8 | 9 | 10

4. The maximum value is dp[4,8] = 10, which can be achieved by selecting items 1, 2, and 3 (weights 2, 3, and 4, values 3, 4, and 5).

3. Coin Change Problem

The Coin Change problem asks for the minimum number of coins needed to make a given amount of change, given a set of coin denominations.

/// <summary>
/// Finds the minimum number of coins needed to make a given amount.
/// </summary>
/// <param name="coins">Array of coin denominations.</param>
/// <param name="amount">The target amount.</param>
/// <returns>The minimum number of coins needed, or -1 if it's not possible.</returns>
public int CoinChange(int[] coins, int amount)
{
    // Initialize dp array with amount + 1 (which is greater than the maximum possible number of coins)
    // dp[i] represents the minimum number of coins needed to make amount i
    int[] dp = new int[amount + 1];
    Array.Fill(dp, amount + 1); // Fill with a value larger than any possible solution
    
    // Base case: 0 coins needed to make 0 amount
    dp[0] = 0;
    
    // Fill the dp array
    for (int i = 1; i <= amount; i++)
    {
        // Try each coin denomination
        foreach (int coin in coins)
        {
            // If the coin value is less than or equal to the current amount
            if (coin <= i)
            {
                // Update the minimum number of coins needed
                // Current minimum vs. 1 (for this coin) + minimum for remaining amount
                dp[i] = Math.Min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    // If dp[amount] is still amount + 1, it means no solution was found
    return dp[amount] > amount ? -1 : dp[amount];
}

Step-by-Step Explanation

Let's trace through finding the minimum coins for amount = 11 with coins = [1, 2, 5]:

1. Initialize dp[0...11] with 12 (amount + 1), and set dp[0] = 0

2. For i=1:

   • For coin=1: dp[1] = min(dp[1], dp[0] + 1) = min(12, 0 + 1) = 1
   • For coin=2: Skip (coin > i)
   • For coin=5: Skip (coin > i)

3. For i=2:

   • For coin=1: dp[2] = min(dp[2], dp[1] + 1) = min(12, 1 + 1) = 2
   • For coin=2: dp[2] = min(dp[2], dp[0] + 1) = min(2, 0 + 1) = 1
   • For coin=5: Skip (coin > i)

4. Continue filling...

5. Final dp array: [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]

6. The minimum number of coins for amount 11 is dp[11] = 3 (one 5-coin and three 2-coins)

4. Edit Distance

The Edit Distance problem finds the minimum number of operations (insertions, deletions, or substitutions) required to convert one string into another.

/// <summary>
/// Calculates the minimum number of operations required to convert word1 to word2.
/// </summary>
/// <param name="word1">First string.</param>
/// <param name="word2">Second string.</param>
/// <returns>The minimum number of operations needed.</returns>
public int EditDistance(string word1, string word2)
{
    int m = word1.Length;
    int n = word2.Length;
    
    // Create a 2D array to store edit distances
    // dp[i,j] represents the minimum operations to convert
    // word1[0...i-1] to word2[0...j-1]
    int[,] dp = new int[m + 1, n + 1];
    
    // Initialize the first row and column
    // dp[i,0] represents the operations to convert word1[0...i-1] to an empty string
    // (which requires i deletions)
    for (int i = 0; i <= m; i++)
        dp[i, 0] = i;
    
    // dp[0,j] represents the operations to convert an empty string to word2[0...j-1]
    // (which requires j insertions)
    for (int j = 0; j <= n; j++)
        dp[0, j] = j;
    
    // Fill the dp table
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            // If the current characters match, no operation needed
            if (word1[i - 1] == word2[j - 1])
            {
                dp[i, j] = dp[i - 1, j - 1]; // No operation needed
            }
            else
            {
                // If characters don't match, take the minimum of:
                // 1. Delete a character from word1: dp[i-1,j] + 1
                // 2. Insert a character into word1: dp[i,j-1] + 1
                // 3. Replace a character in word1: dp[i-1,j-1] + 1
                dp[i, j] = 1 + Math.Min(
                    Math.Min(
                        dp[i - 1, j],     // Deletion
                        dp[i, j - 1]      // Insertion
                    ),
                    dp[i - 1, j - 1]      // Substitution
                );
            }
        }
    }
    
    // The bottom-right cell contains the minimum operations needed
    return dp[m, n];
}

Step-by-Step Explanation

Let's trace through finding the edit distance between "horse" and "ros":

1. Initialize the dp table:

      | "" | r | o | s
   ---|---|---|---|---
   "" | 0  | 1 | 2 | 3
   h  | 1  |   |   |
   o  | 2  |   |   |
   r  | 3  |   |   |
   s  | 4  |   |   |
   e  | 5  |   |   |

2. Fill the table:

   • For i=1, j=1: word1[0] = 'h', word2[0] = 'r', they don't match, so dp[1,1] = 1 + min(dp[0,1], dp[1,0], dp[0,0]) = 1 + min(1, 1, 0) = 1
   • Continue filling...

3. Final dp table:

      | "" | r | o | s
   ---|---|---|---|---
   "" | 0  | 1 | 2 | 3
   h  | 1  | 1 | 2 | 3
   o  | 2  | 2 | 1 | 2
   r  | 3  | 2 | 2 | 2
   s  | 4  | 3 | 3 | 2
   e  | 5  | 4 | 4 | 3

4. The edit distance is dp[5,3] = 3, which means we need 3 operations to convert "horse" to "ros".

5. Longest Increasing Subsequence (LIS)

The LIS problem finds the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

/// <summary>
/// Finds the length of the longest increasing subsequence in an array.
/// </summary>
/// <param name="nums">The input array.</param>
/// <returns>The length of the longest increasing subsequence.</returns>
public int LengthOfLIS(int[] nums)
{
    if (nums.Length == 0)
        return 0;
    
    // dp[i] represents the length of the longest increasing subsequence
    // ending at index i
    int[] dp = new int[nums.Length];
    
    // Initialize all values to 1 (each element is at least a subsequence of length 1)
    Array.Fill(dp, 1);
    
    // Fill the dp array
    for (int i = 1; i < nums.Length; i++)
    {
        // Check all previous elements
        for (int j = 0; j < i; j++)
        {
            // If the current element is greater than the previous element,
            // we can extend the subsequence
            if (nums[i] > nums[j])
            {
                // Update the LIS length if extending the subsequence gives a longer LIS
                dp[i] = Math.Max(dp[i], dp[j] + 1);
            }
        }
    }
    
    // Find the maximum value in the dp array
    return dp.Max();
}

Step-by-Step Explanation

Let's trace through finding the LIS of [10, 9, 2, 5, 3, 7, 101, 18]:

1. Initialize dp = [1, 1, 1, 1, 1, 1, 1, 1]

2. For i=1 (value 9):

   • For j=0 (value 10): 9 < 10, so we can't extend
   • dp[1] remains 1

3. For i=2 (value 2):

   • For j=0 (value 10): 2 < 10, so we can't extend
   • For j=1 (value 9): 2 < 9, so we can't extend
   • dp[2] remains 1

4. For i=3 (value 5):

   • For j=0 (value 10): 5 < 10, so we can't extend
   • For j=1 (value 9): 5 < 9, so we can't extend
   • For j=2 (value 2): 5 > 2, so dp[3] = max(dp[3], dp[2] + 1) = max(1, 1 + 1) = 2

5. Continue filling...

6. Final dp array: [1, 1, 1, 2, 2, 3, 4, 4]

7. The length of the LIS is 4, which corresponds to the subsequence [2, 3, 7, 101] or [2, 3, 7, 18].

Space Optimization in Dynamic Programming

Many DP problems that use 2D arrays can be optimized to use only 1D arrays, significantly reducing space complexity.

Example: Optimized 0/1 Knapsack

/// <summary>
/// Solves the 0/1 Knapsack problem with optimized space complexity.
/// </summary>
/// <param name="weights">Array of item weights.</param>
/// <param name="values">Array of item values.</param>
/// <param name="capacity">Maximum weight capacity of the knapsack.</param>
/// <returns>The maximum value that can be obtained.</returns>
public int KnapsackOptimized(int[] weights, int[] values, int capacity)
{
    int n = weights.Length;
    
    // Use a 1D array instead of a 2D array
    // dp[w] represents the maximum value with capacity w
    int[] dp = new int[capacity + 1];
    
    // Process each item
    for (int i = 0; i < n; i++)
    {
        // Process in reverse to avoid using items multiple times
        // (since we're reusing the same array for all items)
        for (int w = capacity; w >= weights[i]; w--)
        {
            // Update the maximum value for capacity w
            dp[w] = Math.Max(dp[w], values[i] + dp[w - weights[i]]);
        }
    }
    
    return dp[capacity];
}

Key Insight

The key insight for this optimization is that when processing item i, we only need the results from item i-1. By processing the weights in reverse order, we ensure that we don't use the same item multiple times (which would happen if we processed from left to right, since we'd be using the updated values from the current item).

How to Approach Dynamic Programming Problems

Step 1: Identify if it's a DP Problem

Look for these characteristics:

• Overlapping Subproblems: The same subproblems are solved multiple times
• Optimal Substructure: The optimal solution contains optimal solutions to subproblems
• Decision Making: The problem involves making choices that affect future decisions

Common problem types include:

• Optimization problems (maximize/minimize something)
• Counting problems (how many ways to...)
• Yes/no problems (is it possible to...)

Step 2: Define the State

The state represents the subproblem you're solving. Ask yourself:

• What information do I need to solve this subproblem?
• What are the changing parameters in the recursive calls?

For example:

• In the Knapsack problem: the state is (i, w) - the first i items with capacity w
• In the LCS problem: the state is (i, j) - the LCS of the first i characters of string1 and the first j characters of string2

Step 3: Formulate the Recurrence Relation

The recurrence relation defines how the solution to a subproblem relates to the solutions of smaller subproblems.

For example:

• In the Knapsack problem: dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w-weights[i-1]])
• In the LCS problem: dp[i][j] = dp[i-1][j-1] + 1 if text1[i-1] == text2[j-1], else max(dp[i-1][j], dp[i][j-1])

Step 4: Identify the Base Cases

Base cases are the simplest subproblems that can be solved directly.

For example:

• In the Knapsack problem: dp[0][w] = 0 for all w (no items means no value)
• In the LCS problem: dp[0][j] = dp[i][0] = 0 (LCS of an empty string with any string is 0)

Step 5: Decide on the Implementation Approach

Choose between:

• Top-down (Memoization): Start with the original problem and recursively solve subproblems
• Bottom-up (Tabulation): Start with the base cases and build up to the original problem

Step 6: Implement and Test

Implement your solution and test it with small examples to verify correctness.

Common Patterns in DP Problems

1. Linear Sequence DP: Problems where the state depends on previous states in a linear sequence (e.g., Fibonacci, LIS).

2. Two-Sequence DP: Problems involving two sequences where the state depends on positions in both sequences (e.g., LCS, Edit Distance).

3. Grid DP: Problems involving a 2D grid where the state depends on adjacent cells (e.g., minimum path sum, unique paths).

4. Interval DP: Problems where the state represents an interval of the input (e.g., matrix chain multiplication, optimal BST).

5. Bitmasking DP: Problems where the state includes a bitmask to represent a subset of items (e.g., traveling salesman problem, subset sum).

Conclusion

Dynamic programming is a powerful technique for solving complex problems efficiently. By breaking down problems into smaller subproblems and avoiding redundant calculations, DP can transform exponential-time algorithms into polynomial-time solutions.

The key to mastering dynamic programming is practice. Start with simpler problems like Fibonacci and gradually work your way up to more complex ones like the Knapsack problem or Edit Distance. With time and experience, you'll develop an intuition for identifying and solving DP problems.

Remember the core principles:

1. Identify overlapping subproblems
2. Define the state clearly
3. Formulate the recurrence relation
4. Identify the base cases
5. Choose the appropriate implementation approach

By following these steps, you'll be well on your way to solving even the most challenging dynamic programming problems.