Dynamic Programming
Optimization techniques for overlapping subproblems using memoization and tabulation.
Fibonacci (Dynamic Programming)
Classic DP problem with memoization to avoid redundant calculations.
How it works
Fibonacci demonstrates the power of DP by caching results of subproblems. Instead of recalculating fib(n-1) and fib(n-2) multiple times, we store them. This reduces time from exponential O(2^n) to linear O(n). DP has two approaches: memoization (top-down, recursive) and tabulation (bottom-up, iterative).
Time Complexity
O(n)
Space Complexity
O(n)
def fib(n, memo={}):
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]0/1 Knapsack (Dynamic Programming)
Classic DP optimization problem with capacity constraints.
How it works
The 0/1 Knapsack problem uses a 2D DP table where dp[i][w] represents the max value using first i items with capacity w. For each item, we decide to include it (if it fits) or exclude it. This is a foundational DP problem teaching the concept of state transitions and optimal substructure.
Time Complexity
O(n*W)
Space Complexity
O(n*W)
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
if 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][capacity]