Imagine you're filling out a massive, tedious tax form. Every few pages, you encounter a complex calculation—say, calculating your total deductible expenses based on a specific set of rules. Now, you could spend twenty minutes re-calculating that same number every single time it's mentioned on a different page, or you could just scribble the result on a Post-it note and stick it to the edge of your monitor. The next time the form asks for that number, you don't do the math; you just glance at the Post-it.

That is the essence of Dynamic Programming (DP). At its heart, DP is just "recursion with a memory." We take a problem that can be broken down into smaller, overlapping sub-problems and ensure we only solve each unique sub-problem exactly once.

The "I've Been Here Before" Technique

In Python, the most intuitive way to implement this is through Memoization. This is the "Post-it note" approach. You write your function recursively, but before you do any heavy lifting, you check a dictionary to see if you've already solved this specific version of the problem.

Let's look at the "Coin Change" problem. If I give you a set of coin denominations (like [1, 2, 5]) and ask for the minimum number of coins to make a target amount (like 11), a naive recursive approach would calculate the same values over and over again. Here is how we fix that using a memo dictionary:

def min_coins_memo(coins, amount, memo=None):
    if memo is None:
        memo = {}
    
    # Base cases
    if amount == 0: return 0
    if amount < 0: return float('inf')
    
    # Check our "Post-it note"
    if amount in memo:
        return memo[amount]
    
    res = float('inf')
    for coin in coins:
        # We try every coin and find the minimum path
        sub_problem = min_coins_memo(coins, amount - coin, memo)
        res = min(res, sub_problem + 1)
    
    # Save the result before returning
    memo[amount] = res
    return res

I personally love memoization because it allows you to keep the logic "top-down"—you start with the big goal and break it down naturally. It's often easier to reason about during a whiteboard interview.

Building the Foundation First

There's a second way to do this called Tabulation. Instead of starting at the top and looking down, you start at the very bottom (the simplest case) and build a table (usually a list) until you reach your target. It's like building a house: you can't put up the roof until the first floor is solid.

In the coin change example, we'd create a list where each index represents an amount from 0 up to our target. We fill in the minimum coins needed for $1, then $2, and so on, using the values we already calculated for smaller amounts.

def min_coins_tab(coins, amount):
    # Initialize a table with a value larger than any possible answer
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # Base case: 0 coins needed to make 0 amount
    
    for i in range(1, amount + 1):
        for coin in coins:
            if i - coin >= 0:
                # The answer for 'i' is the min of its current value 
                # or the answer for (i - coin) plus this one coin
                dp[i] = min(dp[i], dp[i - coin] + 1)
                
    return dp[amount] if dp[amount] != float('inf') else -1

Choosing Your Weapon: Top-Down vs. Bottom-Up

You might be wondering which one to use. Here is my rule of thumb:

• Use Memoization when the state space is sparse. If you don't actually need to solve every single sub-problem to get to the final answer, memoization is faster because it only computes what it needs.
• Use Tabulation when you know you'll need to solve almost all the sub-problems anyway. It avoids the overhead of recursive function calls (which can lead to a RecursionError in Python if the input is too large) and is generally more memory-efficient.

The key is recognizing the "Optimal Substructure." If you can say, "The best way to solve this big problem is just a combination of the best ways to solve these smaller versions of the problem," you're in DP territory.

📋 Practical Task

Implementing a Minimum-Path-Sum Grid Solver

Imagine a robot starting at the top-left corner (0, 0) of a grid filled with numbers. The robot can only move down or right. Your goal is to find the path from the top-left to the bottom-right that minimizes the sum of the numbers along the way.

Your Task: Write a function min_path_sum(grid) that takes a 2D list of integers and returns the minimum sum possible. You must use either a Memoization or Tabulation approach to ensure the time complexity is O(M * N), where M and N are the dimensions of the grid.

Example Input:

grid = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]