Lecture from: 24.10.2024 | Video: Videos ETHZ | Official Script

Dynamic Programming

Dynamic programming is a powerful technique that empowers even mere mortal programmers to tackle complex problems. It builds upon the idea of using invariants, similar to what we explored in sorting algorithms.

Instead of directly solving a problem, dynamic programming breaks it down into smaller overlapping subproblems and recursively solves them. The key difference lies in storing the results of these subproblems to avoid redundant calculations, leading to significant efficiency gains.

Recursion: A Primer

Let’s illustrate this with the classic Fibonacci sequence example:

Pseudocode:

def fibonacci(n) {
  if n <= 2 → f = 1
  else f = fibonacci(n-1) + fibonacci(n-2)
  return f
}

This recursive approach defines fibonacci(n) in terms of two smaller Fibonacci values. However, repeated calculations for the same subproblems lead to exponential time complexity.

Runtime Analysis of Fibonacci

Let’s analyze the runtime complexity of our recursive Fibonacci implementation:

  • Base Cases: where ‘c’ is some constant (representing the time for the base cases).
  • Recursive Step: where ‘d’ is another constant (accounting for additional operations within the recursive step).

Notice how this recurrence relation resembles the Fibonacci sequence calculation itself! This similarity is crucial to understanding the runtime.

Using Induction: We can use induction to show that: .

Where represents the nth Fibonacci number. (See exercise 3.4 for more info on how we deduced this…)

Therefore, the runtime complexity of this recursive Fibonacci implementation is exponential, specifically .

This begs the question: what can we do to combat this inefficiency?

Memoization (Solution 1)

Memoization provides a powerful technique to optimize our recursive Fibonacci implementation.

Instead of recalculating Fibonacci numbers repeatedly, we store the results of previously computed values in a data structure like an array or dictionary. This avoids redundant calculations, significantly improving performance.

Let’s illustrate this with Python and a memo array:

Pseudocode:

def fib_memo(n, memo=[]):
  if n <= 2:
    return 1
  if memo[n] != None:
    return memo[n] 
  else:
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]
 
print(fib_memo(6)) # Output: 8

Explanation:

  • We initialize an empty list memo to store calculated Fibonacci numbers.
  • Before each recursive call, we check if the result for n is already in memo. If it is, we directly return the stored value. Otherwise, we calculate the Fibonacci number recursively and store it in memo before returning.

Runtime: 

Memoization dramatically reduces the runtime complexity from exponential to linear . This is because each Fibonacci number is calculated only once and subsequently retrieved from the memo array, resulting in a single pass through the problem space.

Iterative Solution (Solution 2)

While memoization optimizes recursion, an iterative approach can be even more efficient and often easier to understand. This “bottom-up” solution builds the Fibonacci sequence incrementally from smaller values up to the desired n.

Pseudocode:

def fibonacci(n):
  if n <= 1:
    return n
  a = 0
  b = 1
  for i in range(2, n+1):
    c = a + b
    a = b
    b = c
  return b

Runtime: The iterative solution has a runtime complexity of . We perform a fixed number of iterations (from 2 to n), making the time proportional to the input size.

The Core Idea

Dynamic programming (DP) hinges on a powerful concept: breaking down complex problems into smaller, overlapping subproblems. These subproblems can often be solved recursively, but DP’s real magic lies in how we handle these solutions.

We aim to solve each subproblem only once and store its result. This eliminates redundant calculations, leading to significant efficiency gains. DP offers various strategies for tackling these subproblems:

  • Top-Down: Start with the main problem and recursively break it down into smaller subproblems. Techniques like memoization (storing results in a table) are often used in top-down approaches.
  • Bottom-Up: Solve the smallest subproblems first and progressively build up to the larger ones. This often involves iteratively computing solutions for increasing input sizes.

Max Subarray Problem Revisited

Let’s revisit the classic “Max Subarray Sum” problem from previous lectures (03 Max Subarray Sum): Given an array of numbers, find the contiguous subarray with the largest sum.

Subproblem Definition: The key insight is that to find the maximum sum subarray ending at index j, we can use the result of the maximum sum subarray ending at index j-1. This forms our recursive relationship:

max_subarray_sum(j) = max(arr[j], max_subarray_sum(j-1) + arr[j], 0)

By clearly defining the subproblem and establishing a recursive relationship, we pave the way for efficient dynamic programming solutions.

Jump Game

Leetcode: Jump Game II

Problem: Given an array of positive (non-zero) numbers A[1..n] representing the maximum jump length from each position, determine the minimum number of jumps required to reach the last element, A[n], starting from position 1.

Input: An array of positive integers A[1..n] where n represents the total number of elements in the array.

Game Rules:

  • Start at position 1 of the array.
  • From any position i, you can jump to any position j where i + 1 ≤ j ≤ i + A[i].

Objective: Find the minimum number of jumps needed to reach the last element, A[n].

Let’s solve this.

Try 1: Breaking Down the Problem

Define a subproblem:

Consider an example array A = [1, 3, 5, 3, 2, 1, 2, 4, 4, 2, 9]. How do we solve for S[8]?

To reach index 8, consider the positions reachable in one jump:

  • Jump to position 8 from position 3 (since A[3] = 5 and 3 + 5 >= 8).
  • Jump to position 8 from position 7 (since A[7] = 4 and 7 + 4 >= 8).

Thus, the solution for S[8] is:

This generalizes to our recursive relationship for any index i:

In other words, find the minimum jump count from reachable positions one step earlier.

Bottom-Up Implementation

Let’s implement a bottom-up solution to calculate the minimum jumps required.

Pseudocode:

def jump_game(A):
    n = len(A)
    S = [float('inf')] * (n + 1)
    S[1] = 0
    
    for i in range(2, n + 1):
        for j in range(1, i):
            if j + A[j] >= i:
                S[i] = min(S[i], S[j] + 1)
                
    return S[n]

Explanation:

  1. Initialization: Create a list S of size n+1 filled with infinity (float('inf')), representing the minimum jumps needed to reach each index, initially assuming all indices are unreachable. Set S[1] to 0 because it takes zero jumps to reach the starting position.
  2. Iteration: For each index i from 2 to n, consider all possible jumping positions j from 1 to i-1. If a jump from position j is valid (i.e., j + A[j - 1] >= i), update S[i] to be the minimum of its current value and 1 + S[j]. This represents taking one jump from position j and adding the minimum jumps needed to reach j.
  3. Return: Finally, return S[n], which contains the minimum jumps required to reach the last index n.

Runtime Complexity

This bottom-up approach has a runtime complexity of .

  • Outer Loop: The outer loop iterates n times (for each index i).
  • Inner Loop: For each i, the inner loop potentially iterates up to i times (considering all possible jumping positions j).

Mathematically, we can express this as: The nested loop structure results in a quadratic time complexity.

Try 2: Switching Perspectives - Geht es besser?

Yes, we can potentially solve this problem more efficiently. Instead of focusing on the position S[i] (minimum jumps to reach index i), let’s consider the maximum reachable index given a certain number of jumps:

Thus, we redefine the problem in terms of reachable positions for each jump count ().

Note for readers: Since I probably wasn’t the only one slightly confused with what’s going on, I suggest watching this video explaining the efficient approach…

This change in perspective leads to a more efficient solution. Let’s illustrate with an example using A = [1, 3, 5, 3, 2, 1, 2, 4, 4, 2, 9].

Example: To find M[3] (the maximum index reachable with 3 jumps), build upon M[2]:

  • With M[2], we can reach indices 0 through 4.
  • For each i within that range (M[2] <= i), consider the position i + A[i] reachable with one more jump (from M[2]).

Recursive Formulation:

We start with . To compute for recursively, we consider all positions reachable with at most jumps—i.e., positions . From each such position , we can jump up to , so the maximum index reachable with jumps is:


This formulation builds the reachable indices iteratively by considering jumps from the previously reachable positions.

Pseudocode:

def jump_game(A):
    k = 0
    M = [0] * (len(A) + 1)
    M[0] = 1
    
    while M[k] < len(A):
        k += 1
        M[k] = max(i + A[i] for i in range(1, M[k-1] + 1))
    
    return k

Optimization of the Recurrence

Looking closer at the recurrence formula for , we see that to compute , it suffices to consider only the indices that require exactly jumps to reach, rather than all reachable with jumps. These indices are the ones that satisfy:

This gives an improved recurrence relation:

with the additional base case .

Pseudocode:

def jump_game(A):
    k = 0
    M = [0] * (len(A) + 1)
    M[0] = 1
    
    while M[k] < len(A):
        k += 1
        # FYI: range(excl M[k-2] and incl M[k-1])
        M[k] = max(i + A[i] for i in range(M[k-2]+1, M[k-1] + 1))
    
    return k

This optimized recurrence allows us to reduce the runtime of the algorithm to , as each index contributes to only one maximum calculation across the entire process.

Lower Bound

The time complexity of is optimal for this problem. To demonstrate this, we can construct a worst-case input where any algorithm must examine each element at least once.

Consider the array . Here, we must read all entries except the last to correctly compute the solution since each entry directly affects the reachability of subsequent indices. Any algorithm must read all entries, thus guaranteeing a worst-case time complexity of for this problem.

Longest Common Subsequence

Leetcode: Longest Common Subsequence

Problem: Given two strings, A and B, find the length of their longest common non-contiguous subsequence. Input: Two strings, A and B, consisting of lowercase English letters. Output: The length of the longest common non-contiguous subsequence of A and B.

Example

Input:
A = "rabbbit"
B = "rabbit"

Output:
5  // "rabbi" is a common non-contiguous subsequence of length 5.

Input:
A = "tiger"
B = "ziege"

Output:
3 // "ige" is a common non-contiguous subsequence of length 3.

Understanding Non-Contiguous Subsequences

  • A subsequence is a sequence formed by deleting some (or no) characters from another sequence without changing the order of the remaining characters. For example, “ten” and “tin” are subsequences of “kitten”.
  • A non-contiguous subsequence allows gaps between chosen characters. “rabbi” is a non-contiguous subsequence of “rabbbit”.

This problem type has wide applications in computer science, including:

  • Bioinformatics: Analyzing similarities and differences between DNA sequences.
  • Text Processing: Finding common patterns or motifs within large text corpora.

Attempt 1: Subproblem A[1..i] and B[1..i]

While thinking about subproblems (A[1..i], B[1..i]) is a good start, simply carrying over the LCS from the previous subproblem won’t always work. We need to consider all possible substrings and their contributions to the overall LCS.

The Flaw:

Imagine A = “tiger” and B = “ziege”. At i = 4, the LCS of A[1..4] (“tige”) and B[1..4] (“zieg”) is 2 (we find “ie”). However, at i = 5, the correct LCS becomes 3 (“ige”). We can’t directly derive this from the previous subproblem’s result because we need to account for the potential inclusion of ‘e’ from B.

The Challenge:

We’d have to analyze every possible substring combination up to i = 5 to find the true LCS. This becomes computationally expensive and inefficient.

Attempt 2: Subproblem Definition and Recursion – A Deeper Dive

Note to reader: Here too, I suggest watching this great video…

Let’s shift our focus towards a more structured approach using subproblems and recursion.

We aim to define a subproblem that represents the LCS (Least Common Subsequence) of two subsequences, A[1..i] and B[1..j], denoted as L[i, j]. Our goal is to build a recursive relationship that allows us to calculate L[i, j] based on smaller subproblems.

Breaking Down the Problem:

We can express this subproblem recursively based on three key cases:

  1. Base Case (Empty Subsequences): If either sequence is empty (i = 0 or j = 0), there are no common elements, so the LCS is 0.

  2. Matching Characters: If the last characters of both subsequences (A[i] and B[j]) match, we can include this character in our LCS. The remaining LCS is then calculated by considering the subsequences without their last elements:

  3. Non-Matching Characters: If A[i] and B[j] don’t match, we consider two possibilities:

  • Include the character a_i from A and calculate the LCS of A[1..i-1] and B[1..j]:
  • Include the character b_j from B and calculate the LCS of A[1..i] and B[1..j-1]:
  • We choose the option that yields a longer LCS:

Combining the Cases:

Finally, we combine these three cases into a single recursive formula:

Bottom-Up Approach

The bottom-up approach offers an efficient way to compute the longest common subsequence (LCS) by systematically filling a 2D table, reflecting the subproblem solutions as we go. Think of this table as a grid where each cell represents the LCS length for specific prefixes of our input strings A and B.

Pseudocode:

def longest_common_subsequence(A, B):
    n, m = len(A), len(B)
    L = [[0] * (m + 1) for _ in range(n + 1)]  
 
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if A[i - 1] == B[j - 1]:
                L[i][j] = 1 + L[i - 1][j - 1]
            else:
                L[i][j] = max(L[i][j - 1], L[i - 1][j])
 
    return L[n][m]

Explanation:

  1. Table Initialization: We create a L table of size (n+1) x (m+1), filled with zeros initially. Each cell L[i][j] will store the length of the LCS for substrings A[0..i-1] and B[0..j-1]. The extra row and column handle empty substring cases.
  2. Table Filling: We iterate through each character position i in string A and j in string B.
    • If A[i-1] matches B[j-1], the LCS length increases by 1 compared to the diagonal cell (L[i-1][j-1]).
    • Otherwise, we take the maximum LCS length from the cell above (L[i-1][j]) or to the left (L[i][j-1]).
  3. Result Extraction: The final result, the length of the LCS for A and B, is stored in L[n][m].

Note that after filling the table, we backtrack from L[n][m] (the bottom-right corner) to reconstruct the actual LCS.

  • If A[i-1] equals B[j-1], it’s part of the LCS, so we add it to the beginning of the lcs string and move diagonally up-left (i-=1j-=1).
  • Otherwise, we move either up (i -= 1) or left (j -= 1) based on which cell has a larger value in the table.

Time Complexity

The time complexity of this bottom-up approach is , which translates to when both input strings, A and B, have a length of approximately N. While this is efficient for many cases, the question remained: geht es besser?

It turns out that under certain assumptions, a slight improvement to is possible, although the implementation is quite complex. The real question was whether more substantial improvements were achievable – could we find an algorithm with a time complexity of for some ? This remained open for decades.

Finally, in 2015, two mathematicians/computer scientists provided a definitive answer: no, such a substantial improvement is impossible.

Edit Distance

Leetcode: Edit Distance

This problem tackles the classic concept of edit distance, which quantifies the minimum number of operations required to transform one string into another. Think of it as the “distance” between two strings in terms of insertions, deletions, or substitutions.

Given two strings A and B, return the minimum number of operations needed to convert A into B. The allowed operations are:

  • Insertion: Add a character to A.
  • Deletion: Remove a character from A.
  • Substitution: Replace a character in A with a different character.

Input:

  • Two strings, A and B, consisting of lowercase English letters.

Output:

  • An integer representing the minimum edit distance between A and B.

Example:

Input: word1 = "horse", word2 = "ros"
Output: 3 

Explanation: 
- One way to transform "horse" to "ros" is:
    - Delete "h":  "orse"
    - Delete "e":   "ors"
    - Substitute 's' for 'r': "ros"

Let’s break down how to solve the Edit Distance problem using a recursive approach.

Understanding the Problem

The goal is to find the minimum number of edits (insertions, deletions, or substitutions) needed to transform one string (word1) into another (word2).

Note to the reader: Once again, I suggest watching this video…

Defining the Recursive Relation

Let ED(i, j) represent the edit distance between the first i characters of word1 and the first j characters of word2. We can express this recursively:

ED(i, j) = min( 
    1 + ED(i - 1, j), // Deletion case: Remove A[i]
    1 + ED(i, j - 1), // Insertion case: Insert B[j]
    ED(i - 1, j - 1) + (A[i] != B[j])  // Substitution case: Replace A[i] if needed
)

Explanation:

  • Deletion Case (1 + ED(i - 1, j)): If the last character of word1 (A[i]) is not present in word2, we need to delete it. The edit distance becomes 1 plus the distance between the remaining substrings ( ED(i - 1, j) ).
  • Insertion Case (1 + ED(i, j - 1)): If the last character of word2 (B[j]) is not present in word1, we need to insert it. The edit distance becomes 1 plus the distance between word1 and the remaining substring of word2 (ED(i, j - 1)).
  • Substitution Case (ED(i - 1, j - 1) + (A[i] != B[j])): If the last characters of both strings match (A[i] == B[j]), no operation is needed. Otherwise, we need a substitution, adding 1 to the distance between the remaining substrings (ED(i - 1, j - 1)).

Base Cases:

  • ED(0, 0) = 0: The edit distance between empty strings is 0.
  • ED(i, 0) = i: To transform an i-character string into an empty one, we need i deletions.
  • ED(0, j) = j: To transform an empty string into a j-character string, we need j insertions.

Pseudocode:

def editDistance(word1: str, word2: str) -> int:
    n = len(word1)
    m = len(word2)
 
    # Create a 2D array to store calculated distances
    dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
 
    # Base cases
    for i in range(n + 1):
        dp[i][0] = i  # Cost of deleting characters from word1 to match empty word2
    for j in range(m + 1):
        dp[0][j] = j  # Cost of inserting characters into word1 to match empty word2
 
    # Fill the dp array using recursion
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # No operation needed, cost is the same as previous subproblem
            else:
                dp[i][j] = min(
                    dp[i - 1][j] + 1,  # Deletion case
                    dp[i][j - 1] + 1,  # Insertion case
                    dp[i - 1][j - 1] + 1,  # Substitution case
                )
    return dp[n][m]  # The final edit distance is at the bottom right corner

Runtime

The runtime complexity of this recursive solution is , where n and m are the lengths of the input strings. This is because we visit each cell in the dp array exactly once.