Dynamic Programming Basics

Welcome to our lesson on Dynamic Programming! This powerful technique is invaluable for tackling complex problems in optimization, combinatorics, and beyond. Dynamic Programming allows you to approach problems by breaking them down into subproblems and storing results of these smaller calculations for future reference.

This method prevents redundant calculations, significantly enhancing the efficiency of your solutions!

One of the classic examples to illustrate Dynamic Programming is calculating the Fibonacci series. When you compute the N-th Fibonacci number recursively, smaller subproblems overlap, and without optimization, this leads to exponential time complexity.

By using Dynamic Programming, specifically memoization, we can save the results of these overlapping subproblems in a table, allowing us to retrieve them directly instead of recalculating each time. This reduces time complexity dramatically.

Here's an example:

def fibonacci(n, memo = {})
  # Return the cached result if it exists
  return memo[n] if memo.key?(n)
  
  # Base cases: fibonacci(0) = 0, fibonacci(1) = 1
  return n if n <= 1
  
  # Compute and cache the Fibonacci number
  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
  
  # Return the computed Fibonacci number
  memo[n]
end

# Test case
puts fibonacci(10)  # Output: 55

1. Memoization Check:

   return memo[n] if memo.key?(n)

   Before performing any calculations, the function checks if the n-th Fibonacci number has already been computed and stored in the memo hash. If it exists, the cached value is returned immediately, avoiding redundant computations.

2. Base Cases:

   return n if n <= 1

   The Fibonacci sequence is defined such that fibonacci(0) = 0 and fibonacci(1) = 1. These base cases terminate the recursion.

3. Recursive Computation and Caching:

   memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)

   For n > 1, the function recursively computes fibonacci(n - 1) and fibonacci(n - 2), sums them up, and stores the result in the memo hash for future reference.

4. Returning the Result:

   memo[n]

   After computing, the function returns the n-th Fibonacci number, now stored in memo[n].