🚀 Dynamic Programming in Python
Dynamic Programming (DP) is a method used in programming to solve complex problems by breaking them down into simpler
subproblems. It is particularly useful when the problem can be divided into overlapping subproblems with optimal
substructure.
🧠 What is Dynamic Programming?
Dynamic Programming is an optimization technique that:
- Solves each subproblem only once.
- Stores (or "memoizes") the result.
- Reuses the result in future calculations.
It’s widely used in problems like:
- Fibonacci sequence
- Knapsack problem
- Longest common subsequence
- Matrix chain multiplication
🧩 Why Use DP?
Without DP, you may solve the same subproblem multiple times, which is inefficient.
Example: Naive Fibonacci (Exponential Time)
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
print(fib(10)) # Output: 55
❌ This solution recalculates the same values many times.
✅ Optimized Fibonacci using DP (Memoization)
def fib_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
print(fib_memo(10)) # Output: 55
✅ Memoization stores results of subproblems to avoid recomputation.
🧮 Bottom-Up DP (Tabulation)
Build the solution from the ground up.
def fib_tab(n):
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]
print(fib_tab(10)) # Output: 55
🗒 Tabulation uses iteration and a table to store results.
📦 Key Components of DP
- Subproblems: Break the problem into smaller chunks.
- Optimal Substructure: Solution of the problem can be built from solutions of subproblems.
- Overlapping Subproblems: Same subproblems appear multiple times.
🎯 Example: 0/1 Knapsack Problem
Given weights and values, determine the maximum value you can carry in a bag of capacity W.
def knapsack(W, weights, values, n):
dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
for i in range(n + 1):
for w in range(W + 1):
if i == 0 or w == 0:
dp[i][w] = 0
elif weights[i - 1] <= w:
dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w])
else:
dp[i][w] = dp[i - 1][w]
return dp[n][W]
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print(knapsack(capacity, weights, values, len(values))) # Output: 220
🛠 Tips for Solving DP Problems
- Identify subproblems.*
- Decide if memoization (top-down) or tabulation (bottom-up) is better.
- Create a recursive or iterative relation.
- Use arrays or dictionaries to store results.
- Visualize the problem with a table/graph if needed.
🧪 Practice Problems
| Problem | Description |
|---|---|
| Fibonacci Numbers | Basic DP example |
| Climbing Stairs | Count ways to reach top |
| 0/1 Knapsack | Max value under capacity |
| Longest Common Subsequence | Similar strings analysis |
| Coin Change | Fewest coins to make amount |
📝 Summary
- ✅ Avoid redundant calculations
- ✅ Solve subproblems once
- ✅ Store results (memo or table)
- ✅ Top-down (recursion + memo) OR bottom-up (loop + tabulation)
🔗 References
Python DP Examples
GeeksforGeeks DP Guide
Created with ❤️ by Pynfinity
