Dynamic Programming

01 Recapping the Problem from Last Lesson: The Coin Trap

In our study of greedy algorithms, we analyzed a counter-example where coin denominations deviated from canonical values:

Our objective was to make change for \$6 using the absolute minimum count of coins (Target = 6).

Greedy failed because it lacked foresight and could not backtrack. But how can an algorithm guarantee a 100% optimal answer without needlessly checking trillions of brute-force combinations?

Enter the crowning jewel of computer science optimization: Dynamic Programming.

02 What is Dynamic Programming?

In essence, the foundational mission of Dynamic Programming is: "To eliminate repeated and redundant computational work."

03 A Classic Example: The Fibonacci Sequence

The Fibonacci sequence is defined across numbers where each term equals the sum of its immediate predecessors:

Formally represented as:

\(F(n) = F(n-1) + F(n-2)\)

For instance, to evaluate \(F(5)\):

Notice what is happening: the subproblem F(3) is required by both \(F(5)\) and \(F(4)\). Similarly, F(2) is needed in multiple separate branches!

04 The Catastrophe of Naive Recursion: Exponential Explosion (\(O(2^n)\))

Standard introductory programming courses often present Fibonacci as a simple recursive function:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

While concise, invoking fib(5) triggers a severely redundant recursion call tree:

                    fib(5)
                  /        \
             fib(4)          fib(3) [Duplicate 1]
            /      \          /     \
       fib(3)     fib(2)   fib(2)   fib(1)
       /    \      /    \   ...
    fib(2) fib(1) fib(1) fib(0)

05 The Core DP Insight: "Why Not Remember?"

What if we ask ourselves a simple common-sense question:

"Once we calculate fib(3) = 2 for the very first time, can we not write this result in a scratchpad? The next time fib(3) is needed anywhere in the tree, we simply read the notebook rather than recalculating the entire sub-tree!"

Yes! And that modest architectural decision—caching prior answers—transforms an unexecutable \(O(2^n)\) disaster into a lightning-fast \(O(n)\) algorithm!

06 The Two Invariant Pillars of Dynamic Programming

DP cannot be applied arbitrarily. For a problem to be solved via Dynamic Programming, it must satisfy two mathematical axioms:

07 Technique 1: Memoization (The Top-Down Approach)

The word Memoization derives from the Latin memorandum ("to be remembered").

memo = {}

def fib(n):
    if n <= 1:
        return n
        
    # Return immediately if answer already cached
    if n in memo:
        return memo[n]
        
    # Compute and store result in cache before returning
    memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

print(fib(50))  # Instantaneous execution: 12586269025

This is termed Top-Down because we initiate execution from the primary target \(F(50)\), branch downward on demand, and cache answers as the call stack unwinds.

08 Technique 2: Tabulation (The Bottom-Up Approach)

The second, industry-standard implementation strategy is Tabulation.

def fib_tab(n):
    if n <= 1:
        return n
        
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    
    # Fill table iteratively from smallest to largest
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
        
    return dp[n]

Memory builds linearly: 0 → 1 → 1 → 2 → 3 → 5 .... Zero recursion overhead, zero risk of stack overflow, and purely deterministic iteration.

09 Memoization vs. Tabulation: Architectural Trade-offs

10 Solving Coin Change with DP: How the Optimal Answer is Found

Let us revisit our opening coin change problem: Coins = [1, 3, 4] and Target = 6.

Instead of greedily snatching the \$4 coin, Dynamic Programming poses a structured question:

We compute and store the minimum coins needed for all amounts from 0 up to 6:

When evaluating dp[6], the algorithm tests all 3 valid transitions:
\(1 + dp[5] = 1 + 2 = 3\)
\(1 + dp[3] = 1 + 1 = 2\)
\(1 + dp[2] = 1 + 2 = 3\)
The minimum is 2 coins (via the \$3 transition)! DP effortlessly bypasses greedy's blind spot to discover the global optimum.

11 The Anatomy of DP: State & Transition

12 Space Optimization: Slashing Memory from \(O(n)\) to \(O(1)\)

Dynamic Programming does not merely optimize execution time; careful design can also shrink auxiliary memory footprints.

Examine the Fibonacci tabulation table: to evaluate \(F(n)\), we do not actually require the entire array \(dp[0 \dots n]\). We only need the two immediate predecessor values.

def fib_optimized(n):
    if n <= 1:
        return n
        
    prev2 = 0  # F(n-2)
    prev1 = 1  # F(n-1)
    
    for _ in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
        
    return prev1

# Time Complexity: O(n)
# Space Complexity: O(1) — constant space with just 3 variables!

Zero arrays allocated; memory consumption remains strictly flat regardless of input size. This technique is known as Rolling Variables or Sliding Window State Reduction.

13 The 7-Step Architectural Framework for DP Problems

14 Key Takeaways: Engineering Wisdom to Remember