Dynamic Programming (DP Table)

Dynamic Programming (DP) is a technique for solving problems by breaking them into subproblems and storing results to avoid redundant computation. This post introduces DP tables, their use cases, and provides practical Python examples and problems for mastering dynamic programming.

Overview

Dynamic Programming (DP) is a technique used to solve problems by breaking them down into simpler subproblems and storing the results to avoid redundant computations.

A DP table is often used to store solutions to subproblems, typically in a 1D or 2D array.

• Top-down = recursion + memoization
• Bottom-up = iterative DP table filling

🧩 Visualizing Dynamic Programming

Fibonacci DP Table

graph LR
    A[dp0] --> B[dp1]
    B --> C[dp2]
    C --> D[dp3]
    D --> E[dp4]
    E --> F[dp5]
    
    style A fill:#ff9999
    style B fill:#ff9999
    style F fill:#99ff99

2D DP Table (Knapsack)

graph TD
    subgraph "Knapsack DP Table"
        subgraph "Capacity"
            C0[0] --- C1[1] --- C2[2] --- C3[3] --- C4[4] --- C5[5]
        end
        
        subgraph "Items"
            I0[Item 0<br/>w=1, v=15] --- I1[Item 1<br/>w=3, v=20] --- I2[Item 2<br/>w=4, v=30]
        end
        
        subgraph "DP Values"
            V00[0] --- V01[0] --- V02[0] --- V03[0] --- V04[0] --- V05[0]
            V10[0] --- V11[15] --- V12[15] --- V13[15] --- V14[15] --- V15[15]
            V20[0] --- V21[15] --- V22[15] --- V23[20] --- V24[35] --- V25[35]
            V30[0] --- V31[15] --- V32[15] --- V33[20] --- V34[35] --- V35[45]
        end
    end
    
    style V35 fill:#99ff99
    style V25 fill:#ffff99
    style V15 fill:#ffcc99

🛠️ How to Use (Python)

# Example: Fibonacci with bottom-up DP
def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)  # DP table to store results
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]  # Fill table iteratively
    return dp[n]
# Time complexity: O(n), Space complexity: O(n)

# Example:
print(fib(5))  # Output: 5
print(fib(10)) # Output: 55

🧩 Climbing Stairs Step-by-Step

graph TD
    S1[dp1 = 1 base case]
    S2[dp2 = 2 base case]
    S3[dp3 = dp2 + dp1 = 3]
    S4[dp4 = dp3 + dp2 = 5]
    R[Result: 5 ways]

    S1 --> S3
    S2 --> S3
    S3 --> S4
    S4 --> R
    style R fill:#99ff99

Suppose n = 4

• Final result: 5 ways to climb 4 stairs.

📘 Sample Problem 1: Climbing Stairs

You can take 1 or 2 steps. How many distinct ways to climb to the top?

# This function counts the number of ways to climb n stairs (1 or 2 steps at a time).
def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]  # Ways to reach i = sum of previous two
    return dp[n]
# Time complexity: O(n), Space complexity: O(n)

# Example:
n = 4
print(climb_stairs(n))  # Output: 5

🧩 0/1 Knapsack Flow

graph TD
    Start[Start: i=1 w=1 to 5]
    I1[Item 1: w=1 v=15]
    D1[dp1w = max dp0w 15 + dp0w-1]
    I2[Item 2: w=3 v=20]
    D2[dp2w = max dp1w 20 + dp1w-3]
    I3[Item 3: w=4 v=30]
    D3[dp3w = max dp2w 30 + dp2w-4]
    Result[Result: dp35 = 45]

    Start --> I1 --> D1 --> I2 --> D2 --> I3 --> D3 --> Result
    style Result fill:#99ff99

🧩 0/1 Knapsack Flow

Suppose weights = [1, 3, 4], values = [15, 20, 30], capacity = 5

• Final result: 45 (maximum value).

📘 Sample Problem 2: 0/1 Knapsack

Given weights, values, and a capacity, find max value you can carry.

# This function solves the 0/1 Knapsack problem using DP.
def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]  # DP table
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i - 1] <= w:
                # Max of not taking or taking the item
                dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]])
            else:
                dp[i][w] = dp[i - 1][w]
    return dp[n][capacity]
# Time complexity: O(n*capacity), Space complexity: O(n*capacity)

# Example:
weights = [1, 3, 4]
values = [15, 20, 30]
capacity = 5
print(knapsack(weights, values, capacity))  # Output: 45

🔁 Variants

• Space optimized (e.g. 1D DP for Fibonacci)
• State compression (e.g. Bitmask DP)
• Tabulation vs memoization