DSA — Dynamic Programming

What is Dynamic Programming?

Solving complex problems by breaking them into simpler subproblems and storing results.

Two Approaches

Top-Down (Memoization)

def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
    return memo[n]

Bottom-Up (Tabulation)

def fibonacci_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]

Steps for DP

1. Define subproblems
2. Write recurrence relation
3. Determine base cases
4. Compute solution (memo or tabulate)
5. Extract answer

Classic DP Problems

Problem	Recurrence
Fibonacci	F(n) = F(n-1) + F(n-2)
Coin Change	dp[i] = min(dp[i], dp[i-coin] + 1)
Knapsack	dp[i][w] = max(val + dp[i-1][w-wt], dp[i-1][w])
LCS	dp[i][j] = dp[i-1][j-1] + 1 if match

Mini Practice

1. Solve Fibonacci with memoization
2. Implement coin change
3. Solve 0/1 knapsack
4. Find longest common subsequence

Up Next

Continue with Greedy Algorithms — greedy approach.