Advanced Algorithms: Dynamic Programming & Greedy Approaches

TL;DR

Dynamic Programming (DP) solves complex problems by breaking them into overlapping subproblems and storing results to avoid re-computation, often used for optimization. Greedy algorithms make the locally optimal choice at each step, hoping it leads to a global optimum. The key difference is DP considers all subproblem solutions, while greedy doesn't backtrack or reconsider past choices.

1. The Mental Model

Think of Dynamic Programming like building a strong wall brick by brick, ensuring each brick is perfectly placed and reusing existing sturdy sections. Greedy algorithms are more like picking the best-looking brick right now and hoping it works out for the whole wall.

2. The Core Material

You'll often face problems that look complex, and it's not immediately obvious if DP or a greedy approach is best. Let's break down each.

Dynamic Programming (DP)

Photo by Mikhail Nilov on Pexels

DP is all about solving problems by combining the solutions of smaller, simpler, overlapping subproblems. The magic happens when you store the results of these subproblems so you don't have to calculate them again. This technique is called memoization (top-down, recursive with caching) or tabulation (bottom-up, iterative building a table).

DP is typically used for optimization problems (finding the minimum, maximum, longest, shortest, etc.) that have two key properties:

1. Optimal Substructure: The optimal solution to the problem can be constructed from the optimal solutions of its subproblems.
2. Overlapping Subproblems: The same subproblems are encountered repeatedly when solving the larger problem.

A classic example is the Fibonacci sequence: F(n) = F(n-1) + F(n-2). Without DP, calculating F(5) would re-calculate F(3) and F(2) multiple times. With DP, you calculate them once and store.

graph TD
    A["Problem P (e.g., F(5))"] --> B["Subproblem P1 (F(4))"]
    A --> C["Subproblem P2 (F(3))"]
    B --> D["Subproblem P3 (F(3))"]
    B --> E["Subproblem P4 (F(2))"]
    C --> F["Subproblem P5 (F(2))"]
    C --> G["Subproblem P6 (F(1))"]
    D -- Reused --> C
    E -- Reused --> F
    subgraph DP Process
        Start(["Start"]) --> Identify(["Identify Subproblems"])
        Identify --> BaseCase(["Define Base Cases"])
        BaseCase --> Store(["Store Solutions (Memoization/Tabulation)"])
        Store --> Combine(["Combine Subproblem Solutions"])
        Combine --> OptimalSolution(["Optimal Solution"])
    end

Greedy Approaches

Photo by Myburgh Roux on Pexels

Greedy algorithms make choices that look best at each step. They build a solution piece by piece, always picking the option that offers the most immediate benefit without considering future consequences.

The core idea is:
1. Make a locally optimal choice.
2. Hope this sequence of local optimal choices leads to a globally optimal solution.

Greedy algorithms are often simpler and faster than DP, but they don't always guarantee the globally optimal solution. For them to work correctly, the problem must have:

1. Greedy Choice Property: A global optimum can be reached by making a locally optimal (greedy) choice.
2. Optimal Substructure: Similar to DP, but here, after making a greedy choice, the remaining subproblem must also have an optimal solution that can be found greedily.

A common example is making change with coins: if you want to give change for 37 cents and have quarters (25), dimes (10), nickels (5), and pennies (1), a greedy approach would pick a quarter, then a dime, then a penny, then a penny. This works in most common currency systems but fails in others (e.g., if you only had 1-cent, 3-cent, and 4-cent coins and needed 6 cents – greedy would take 4, then 1, then 1, for 3 coins; optimal is 3, then 3, for 2 coins).

3. Worked Example: Longest Common Subsequence (LCS)

Let's find the LCS of two strings, X = "AGGTAB" and Y = "GXTXAYB". This is a classic DP problem.

Problem: Given two sequences, find the length of the longest subsequence present in both of them. 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.

DP Approach: We'll build a 2D table dp[i][j] where dp[i][j] stores the length of the LCS of X[0...i-1] and Y[0...j-1].

Base Cases:
* dp[0][j] = 0 (LCS with an empty string is 0)
* dp[i][0] = 0 (LCS with an empty string is 0)

Recursive Relation (Bottom-Up):
For i > 0 and j > 0:
* If X[i-1] == Y[j-1] (characters match), then dp[i][j] = 1 + dp[i-1][j-1] (match and add to LCS of previous parts).
* If X[i-1] != Y[j-1] (characters don't match), then dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (take the maximum LCS from either excluding the last char of X or excluding the last char of Y).

Let's fill the table for X = "AGGTAB" (length 6) and Y = "GXTXAYB" (length 7).

Trace:
* dp[1][1] (A vs G): max(dp[0][1], dp[1][0]) = max(0,0) = 0
* dp[1][5] (A vs A): 1 + dp[0][4] = 1 + 0 = 1
* dp[2][1] (G vs G): 1 + dp[1][0] = 1 + 0 = 1
* ...
* dp[6][7] (B vs B): 1 + dp[5][6] = 1 + 3 = 4

The value in dp[6][7] (bottom-right corner) is 4. The LCS length is 4. One possible LCS is "GTAB".

def lcs_length(X, Y):
    m = len(X)
    n = len(Y)

    # Create a 2D array (table) to store results of subproblems
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Fill the dp table in a bottom-up manner
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = 1 + dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

# Example usage:
X = "AGGTAB"
Y = "GXTXAYB"
print(f"Length of LCS is: {lcs_length(X, Y)}") # Output: Length of LCS is: 4

4. Key Takeaways

• Dynamic Programming breaks problems into overlapping subproblems, storing results to avoid redundant calculations (memoization/tabulation).
• Use DP when a problem has optimal substructure and overlapping subproblems, typically for optimization.
• Greedy algorithms make the best local choice at each step, aiming for a global optimum without backtracking.
• Use greedy when the greedy choice property and optimal substructure are present; it's often simpler and faster.
• Not all problems can be solved optimally with a greedy approach; some require the more exhaustive DP.
• If you're solving an optimization problem and see overlapping subproblems, think DP.
• If an immediate best choice always leads to the overall best solution, greedy might work.

Common Mistakes:
- Applying a greedy approach when the greedy choice property doesn't hold, leading to sub-optimal solutions.
- Not identifying or correctly defining the base cases in a DP solution.
- Forgetting to store (memoize/tabulate) subproblem results in DP, which turns it into a slow recursive solution.
- Confusing DP with simple recursion; DP adds memoization/tabulation to optimize.

5. Now Try It

Try to solve the "Coin Change" problem for finding the minimum number of coins. Given a set of coin denominations (e.g., [1, 5, 10, 25]) and a target amount (e.g., 37), write a DP function min_coins(coins, amount) that returns the minimum number of coins needed. What does your dp array store, and what's the recursive relation? Success looks like your function correctly returning 4 for coins=[1,5,10,25], amount=37.