Dynamic Programming

Dynamic Programming (DP) is an algorithmic technique used to solve complex problems by

  • breaking them down into smaller subproblems

  • solving each subproblem only once

  • storing the solutions to subproblems to avoid redundant computation.

Key Characteristics

  1. Divide and Conquer: Break down the problem into smaller subproblems.

  2. Overlapping Subproblems: Subproblems may have some overlap, meaning that some subproblems may be identical or have similar solutions.

  3. Optimal Substructure: The problem can be solved optimally by solving its subproblems optimally.

  4. Memoization: Store the solutions to subproblems to avoid redundant computation.

How Dynamic Programming Works

  1. Identify the problem: Determine if the problem can be solved using DP.

  2. Define the state: Identify the variables that describe the state of the problem.

  3. Define the transition: Determine how to transition from one state to another.

  4. Initialize the DP table: Create a table to store the solutions to subproblems.

  5. Fill the DP table: Iterate over the states, solving each subproblem and storing its solution.

  6. Extract the solution: The solution to the original problem is stored in the DP table.

Types of Dynamic Programming

  1. Top-Down DP: Start with the original problem and recursively break it down into smaller subproblems.

  2. Bottom-Up DP: Start with the smallest subproblems and iteratively build up to the original problem.

Advantages

  1. Efficient: Avoids redundant computation by storing solutions to subproblems.

  2. Scalable: Can solve large problems by breaking them down into manageable subproblems.

  3. Optimal: Guarantees optimal solutions by solving subproblems optimally.

Common Applications

  1. Fibonacci Series

  2. Longest Common Subsequence

  3. Shortest Path Problems

  4. Knapsack Problem

  5. Matrix Chain Multiplication

Example: Fibonacci Series

Problem: Find the nth Fibonacci number.

Top-Down DP Solution

Using recursion:

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

Bottom-Up DP Solution

Using loop iteration:

def fibonacci(n):
    dp = [0] * (n+1)
    dp[1] = dp[2] = 1
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

References