Dynamic Programming

1. The Two Pillars of DP

A problem is a good candidate for DP if it exhibits two key properties:

• Overlapping Subproblems: The problem can be broken down into subproblems that are reused several times. Consider calculating fib(5). This requires fib(4) and fib(3). But calculating fib(4) also requires fib(3). Without DP, we would compute fib(3) twice.
• Optimal Substructure: An optimal solution to the problem can be constructed from the optimal solutions of its subproblems.

Visualizing Overlapping Subproblems: Fibonacci

The naive recursive solution for Fibonacci has exponential time complexity because it re-computes the same values over and over again. DP solves this by storing the results. Use the interactive visualization below to see how many redundant calls are made for even a small number like n=6. This clearly demonstrates the "overlapping subproblems" property.

2. Top-Down vs. Bottom-Up

Memoization (Top-Down)

This is a recursive approach. You write a standard recursive function, but add a cache (like a hash map or array) to store the results of subproblems. Before computing, you check the cache. If the result is there, you return it. Otherwise, you compute the result, store it in the cache, and then return it.

class Solution:
    def fib(self, n: int) -> int:
        memo = {}
        def solve(k):
            if k in memo:
                return memo[k]
            if k <= 1:
                return k
            memo[k] = solve(k - 1) + solve(k - 2)
            return memo[k]
        return solve(n)

Tabulation (Bottom-Up)

This is an iterative approach. You build a table (usually a 1D or 2D array) and fill it up from the smallest subproblem to the largest. This avoids recursion entirely and the associated risk of stack overflow for deep recursion.

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        dp = [0] * (n + 1)
        dp[1] = 1
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

3. Common DP Patterns & Problems

1D DP (Sequences)

These problems typically involve a single array or sequence, and the state dp[i] depends only on previous states (e.g., dp[i-1], dp[i-2]).

Classic Problem: Climbing Stairs - You can climb 1 or 2 steps. How many ways to reach the top? The number of ways to reach step i is the sum of ways to reach i-1 and i-2. This is the Fibonacci sequence!

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        one_step_back, two_steps_back = 2, 1
        for _ in range(3, n + 1):
            current = one_step_back + two_steps_back
            two_steps_back = one_step_back
            one_step_back = current
        return one_step_back

Classic Problem: Coin Change - Find the minimum number of coins to make a certain amount. dp[amount] = 1 + min(dp[amount - coin]) for all available coins.

from typing import List

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        
        for a in range(1, amount + 1):
            for c in coins:
                if a - c >= 0:
                    dp[a] = min(dp[a], 1 + dp[a - c])
                    
        return dp[amount] if dp[amount] != float('inf') else -1

2D DP (Grids & Two Sequences)

These problems often involve a 2D grid or comparing two strings/arrays. The state dp[i][j] depends on values like dp[i-1][j], dp[i][j-1], and dp[i-1][j-1].

Classic Problem: Unique Paths - Find the number of paths to the bottom-right of a grid. The number of paths to cell [i][j] is the sum of paths to the cell above and the cell to the left.

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

Classic Problem: Longest Common Subsequence - Find the length of the longest subsequence common to two strings. If text1[i] == text2[j], the LCS is 1 + LCS of the prefixes. Otherwise, it's the max of the LCS if we exclude one character from either string.

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]
        
        for i in range(len(text1) - 1, -1, -1):
            for j in range(len(text2) - 1, -1, -1):
                if text1[i] == text2[j]:
                    dp[i][j] = 1 + dp[i+1][j+1]
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j+1])
                    
        return dp[0][0]