Dynamic Programming

This note is part of my learning notes on Data Structures & Algorithms.

---

Dynamic Programming

A dynamic programming (DP) problem is a type of problem that can be solved by breaking it down into simpler subproblems, solving each subproblem just once, and storing their solutions - typically using a table to avoid redundant calculations. This approach is particularly useful for optimization problems, where the goal is to find the best solution among many possible ones.

Key Characteristics

• Optimal substructure: The problem can be broken down into smaller subproblems, and the optimal solution to the problem can be constructed from the optimal solutions of its subproblems.
• Overlapping subproblems: The problem can be divided into subproblems which are reused several times. Dynamic programming solves each subproblem once and stores the result to avoid redundant work.

---

SRTBOT Framework

The SRTBOT framework is a systematic approach to solve dynamic programming (DP) problems. It stands for:

• Subproblem
• Recurrence
• Topological order
• Base cases
• Original problem
• Time complexity

---

1. Subproblem

Define the subproblem of the DP. This usually involves defining what each entry in the DP table represents. Typically, the state will be an array or matrix where each element represents the solution to a subproblem.

2. Recurrence

Determine the recurrence relation that relates the current state to previous states. This step involves writing an equation or set of equations that describe how to compute the value of the current state based on previous states.

3. Topological order

Create a table (array or matrix) to store the computed values of subproblems and solve the problem in a bottom-up manner. Initialize this table based on the problem’s constraints.

4. Base cases

Identify and initialize the base cases of your DP table. Base cases are the simplest subproblems that can be solved directly without any further subproblem decomposition.

5. Original problem

Solve the original problem by solving all subproblems.

6. Time complexity

Analyze the time complexity of your solution by considering the size of the table and the number of operations required to fill each entry.

---

Example 1: Fibonacci Sequence

Compute the n-th Fibonacci number.

The Fibonacci sequence is defined as:

• $F(0) =0$
• $F(1) =1$
• $F(n) = F(n-1) + F(n-2)$ for $n \geq 2$

1. Subproblem $dp[i]$ will represent the i-th Fibonacci number $F(i)$
2. Recurrence: $dp[i] = dp[i-1] + dp[i-2]$
3. Create a table (array) to store the computed Fibonacci numbers up to $n$ in topological order.
4. Base cases
   • $dp[0] = 0$
   • $dp[1] = 1$
5. Original problem: $dp[n]$
6. Time complexity:
   • The table has $n+1$ entries
   • Each entry computatin takes $O(1)$ time
   • Overall complexity is $O(n)$

Pseudocode:

def fibonacci(n):
    # Step 3: Table creation
    dp = [0] * (n + 1)
    
    # Step 4: Base cases
    dp[0] = 0
    dp[1] = 1
    
    # Step 5: Original problem
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    # The nth Fibonacci number
    return dp[n]

# Example usage
n = 10
print(f"The {n}th Fibonacci number is {fibonacci(n)}")

---

Example 2: Bowling Problem

In the Bowling problem, you are given a list of integers representing the number of pins knocked down in each throw. The goal is to compute the maximum score possible under the rules of bowling. The rules include the concepts of strikes, spares, and normal throws.

• A strike (all 10 pins knocked down in one throw) earns 10 points plus the sum of the next two throws.
• A spare (all 10 pins knocked down in two throws) earns 10 points plus the sum of the next throw.
  = A normal throw earns the number of pins knocked down.

1. Subproblem: $dp[i]$ will represent the maximum score achievable from the 0th throw to the i-th throw.
2. Recurrence:
   • If throw $i$ is a strike, then $dp[i] = dp[i-1] + 10 + throws[i+1] + throws[i+2]$
   • If throw $i$ and $i-1$ form a spare, then $dp[i] = dp[i-2] + 10 + throws[i+1]$
   • Normal throw, then $dp[i] = dp[i-1] + throws[i]$
3. Create a table (array) to store the computed scores up to each throw in topological order.
4. Base case:
   • $dp[0] = throws[0]$
   • $dp[1] = throws[0] + throws[1]$
5. Original problem: $dp[n-1]$
6. Time Complexity: Since we are filling each entry of the table in constant time, the overall time complexity is $O(n)$

Pseudocode

def bowling_score(throws):
    n = len(throws)
    dp = [0] * (n + 1)
    
    # Step 4: Base cases
    if n == 0:
        return 0
    dp[0] = throws[0]
    if n > 1:
        dp[1] = throws[0] + throws[1]
    
    # Step 5: Original problem
    for i in range(2, n):
        # Check for strike
        if throws[i-1] == 10:
            dp[i] = dp[i-1] + 10 + (throws[i] if i < n else 0) + (throws[i+1] if i+1 < n else 0)
        # Check for spare
        elif throws[i-1] + throws[i-2] == 10:
            dp[i] = dp[i-2] + 10 + (throws[i] if i < n else 0)
        # Normal throw
        else:
            dp[i] = dp[i-1] + throws[i]
    
    return dp[n-1]

# Example usage
throws = [10, 5, 5, 7, 2, 10, 10, 10, 5, 5, 5, 5, 5, 5]
print(f"The maximum score is {bowling_score(throws)}")

---

References

• Solving DP problems by SRTBOT framework