Dynamic Programming (DP) - Memoization is a powerful problem-solving paradigm that can simplify solving complex computational problems. If you’re new to Dynamic Programming - Memoization, understanding memoization is the first step toward mastering this technique. In this post, we’ll break down memoization with an easy-to-understand problem: calculating Fibonacci numbers.
Understanding Recurrence Relation
Before we dive into Dynamic Programming, we need to learn what is a recurrence relation.
A recurrence relation is a mathematical formula that expresses a problem's solution in terms of its smaller subproblems.
Imagine you are building a tower of blocks, and you want to know the total height of the tower.
You notice that each layer depends on the height of the layer below it.
To figure out the height of the 5th layer, you need the height of the 4th layer.
The height of the 4th layer depends on the 3rd, and so on.
This dependency can be expressed as: "The height of a layer is equal to the height of the layer below it plus the size of the new block added."
This is the recurrence relation of the problem. To solve it, you keep going down until you reach the base case (the height of the first layer, which you know).
In this metaphor:
Tower layers = Subproblems
Height of each layer = Solution to each subproblem
Base layer = Base case of the recurrence relation / Height of first layer
By solving each layer step by step, starting from the base, you eventually solve the whole problem (the height of the tower).
A recurrence relation defines how the solution of a problem depends on the solutions of its subproblems. It specifies:
Base Cases: Directly solvable parts of the problem.
Recursive Formula: The relationship between the current problem and its smaller subproblems.
How to Derive a Recurrence Relation ?
Understand the Problem: Break the problem into smaller subproblems and identify overlapping components.
Define Subproblem States: Represent the problem using variables
Relate the States: Express the solution for the current state in terms of its smaller states.
Establish Base Cases: Define simple conditions where the solution is directly known.
What is Dynamic Programming ?
Dynamic Programming involves breaking a problem into smaller overlapping subproblems and solving each just once. It relies on two main techniques:
Memoization (Top-Down Approach): Storing results of subproblems to avoid redundant computations.
Tabulation (Bottom-Up Approach): Iteratively solving subproblems starting from the base cases.
Today, we’ll focus on memoization using the Fibonacci problem as an example.
Dynamic Programming - Memoization Explained with Fibonacci Numbers
The Fibonacci sequence starts by fixing the first two numbers:
The first number is 0.
The second number is 1.
From there, each new number is the sum of the last two numbers.
Number we calculating | First Number to Add | Second Number to Add | Resultant Number | Sequence So Far |
3rd - F(2) | 1st | 2nd | 0 + 1 = 1 | 0 , 1, 1 |
4th - F(3) | 2nd | 3rd | 1 + 1 = 2 | 0, 1, 1, 2 |
5th - F(4) | 3rd | 4th | 1 + 2 = 3 | 0, 1, 1, 2, 3 |
6th - F(5) | 4th | 5th | 2 + 3 = 5 | 0, 1, 1, 2, 3, 5 |
It's like a chain where each link is made by combining the last two links!
Deriving the Recurrence Relation
In the Fibonacci sequence:
The first number is defined as F(0)=0.
The second number is defined as F(1)=1.
The sequence starts from 0, not 1. This means F(0) represents the 0th number.
To calculate the n-th Fibonacci number F(n):
A Fibonacci number is always the sum of its previous two numbers.
This can be expressed as: F(n) = F(n−1) + F(n−2) where:
F(n−1) is the (n−1)-th number.
F(n−2) is the (n−2)-th number.
So, using this formula, you can find the n-th number in the Fibonacci sequence.
Testing the Recurrence Relation
We will use a decision tree which is a flow chart like structure used in programming to make decisions. It splits the data leading to specific outcomes. It helps to see us the subproblems.
Below you will see that in order to calculate F(4), we solve the sub problems F(3) and F(2).
Please note that purple fields are base cases.
In the tree you can see that we store the results going down from F(2), there is no hard and fast rule that we use F(2) only, we can either use F(2) or F(3)
Let's put n = 4
F(n) = F(n-1) + F(n-2)
F(4) = F(4-1) + F(4-2)
F(4) = F(3) + F(2)
From the above table and images we know that F(3) = 4th number = 2 and F(2) = 3rd number = 1. So,
F(4) = 2 + 1 = 3.
We can see that our recurrence relation is working correctly.
How Dynamic Programming - Memoization Works: Step-by-Step
Identify Overlapping Subproblems: Fibonacci numbers require repeated computations for the same inputs.
Use a Cache (Memo): Store results of previously solved subproblems in a dictionary or array.
Avoid Recalculation: Before solving a subproblem, check if its result is already in the cache.
Dynamic Programming - Memoization Implementation in Python
Here’s how you can solve the Fibonacci problem using memoization:
def fib(n):
memo = {} # Initialize a dictionary for memoization
def helper(x):
if x in memo: # Check if the result is already cached
return memo[x]
if x <= 1: # Base cases
return x
memo[x] = helper(x - 1) + helper(x - 2)
# Store result in cache
return memo[x]
return helper(n)Explanation:
The helper function computes Fibonacci numbers recursively.
Before solving F(x), it checks if F(x) is already in memo.
The result is cached to avoid redundant computations.
Time and Space Complexity with Memoization
With memoization, the complexity reduces to linear - O(n), as each subproblem is solved only once. We also use a memo or cache, in this case a dictionary, which store the results which takes up - O(n) space.
Dynamic Programming in Real-World Problems
Understanding Dynamic Programming - Memoization through Fibonacci numbers builds the foundation for tackling real-world problems. DP is commonly used in:
Optimization Problems: Knapsack, coin change, etc.
Sequence Problems: Longest Common Subsequence, Longest Increasing Subsequence.
Game Theory: Minimax problems.
Key Takeaways
Dynamic Programming is a technique to solve problems by breaking them into smaller overlapping subproblems.
Memoization stores results to reduce redundant computations.
The Fibonacci problem is a perfect starting point for learning memoization.
Comments