Python Dynamic Programming (DP) Complete Guide

Dynamic Programming (DP) is one of the most important techniques in algorithm design. It is widely used to solve problems that involve overlapping subproblems and optimal substructure.

In this guide, we will learn DP from basics to advanced level with practical coding examples.

1. What is Dynamic Programming?

Dynamic Programming is an optimization technique that solves complex problems by breaking them into smaller subproblems and storing the results to avoid recomputation.

There are two main approaches: 1. Memoization (Top-Down) 2. Tabulation (Bottom-Up)

2. Memoization (Top-Down)

Example: Fibonacci using memoization

              
            
Python

            memo = {}

def fib(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

print(fib(10))
          

3. Tabulation (Bottom-Up)

Example: Fibonacci using tabulation

              
Python

            n = 10
fib = [0, 1]

for i in range(2, n+1):
    fib.append(fib[i-1] + fib[i-2])

print(fib[n])

4. Classic DP Problems

Problem 1: Climbing Stairs

              
            
Python

            def climb(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n+1):
        a, b = b, a + b
    return b

print(climb(5))
          

Problem 2: 0/1 Knapsack

              
            
Python

            def knapsack(wt, val, W, n):
    dp = [[0]*(W+1) for _ in range(n+1)]

    for i in range(1, n+1):
        for w in range(W+1):
            if wt[i-1] <= w:
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][W]
          

Problem 3: Longest Common Subsequence (LCS)

              
            
Python

            def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0]*(n+1) for _ in range(m+1)]

    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]
          

5. Advanced DP Problems

Problem 4: Coin Change

              
Python

            def coin_change(coins, amount):
    dp = [float('inf')] * (amount+1)
    dp[0] = 0

    for coin in coins:
        for i in range(coin, amount+1):
            dp[i] = min(dp[i], dp[i-coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

Problem 5: Longest Increasing Subsequence (LIS)

              
Python

            def lis(arr):
    dp = [1]*len(arr)

    for i in range(len(arr)):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j]+1)

    return max(dp)

6. DP Patterns

1. Fibonacci pattern.

2. Knapsack pattern.

3. Subsequence problems.

4. Partition problems.

5. Grid-based DP.

7. Optimization Techniques

1. Reduce space complexity using variables.

2. Avoid recomputation with memoization.

3. Use bottom-up approach when possible.

8. Practice Problems

1. Edit Distance.

2. Matrix Chain Multiplication.

3. Subset Sum Problem.

4. Palindrome Partitioning.

5. Word Break Problem.

Conclusion

Dynamic Programming is a powerful technique that transforms exponential problems into polynomial time solutions. Mastering DP requires practice and pattern recognition.

Focus on understanding problem patterns and implementing optimized solutions to excel in coding interviews.