In this video lesson we will learn about memoization and use it to improve the recursive fibonacci algorithm written in the previous lesson:
Problem - Fibonacci:
The Fibonacci numbers, commonly denoted F(n)
form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0
and 1
. That is,
F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), for n > 1.
Write a recursive function with memoization that given n
, returns F(n)
.
Example 1:
Input: n = 2 Output: 1 Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
Example 2:
Input: n = 3 Output: 2 Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
Example 3:
Input: n = 4 Output: 3 Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.
0 <= n <= 30
Your algorithm should run in O(n) time and use O(n) extra space.
Memoization is a powerful optimization technique used to speed up recursive algorithms by storing the results of expensive function calls and reusing them when the same inputs occur again. This technique is particularly useful in dynamic programming and can significantly reduce the time complexity of algorithms.
One common scenario where memoization is useful is in computing the Fibonacci sequence. The naive recursive approach to compute Fibonacci numbers has an exponential time complexity, making it inefficient for large inputs. By using memoization, we can reduce the time complexity to linear time.
The fundamental concept of memoization involves storing the results of function calls in a data structure (usually a hash map or an array) and checking this data structure before making a new function call. If the result is already computed, it is returned immediately, avoiding redundant calculations.
For example, in the Fibonacci sequence, the nth Fibonacci number is the sum of the (n-1)th and (n-2)th Fibonacci numbers. By storing the results of these calculations, we can avoid recomputing them multiple times.
To implement memoization for the Fibonacci sequence, we need to follow these steps:
Let's look at some examples to understand how memoization can be applied to the Fibonacci sequence:
import java.util.HashMap;
import java.util.Map;
public class Fibonacci {
// Create a map to store the results of function calls
private Map<Integer, Integer> memo = new HashMap<>();
// Recursive function with memoization
public int fib(int n) {
// Base cases
if (n == 0) return 0;
if (n == 1) return 1;
// Check if the result is already computed
if (memo.containsKey(n)) {
return memo.get(n);
}
// Compute the result and store it in the map
int result = fib(n - 1) + fib(n - 2);
memo.put(n, result);
return result;
}
public static void main(String[] args) {
Fibonacci fibonacci = new Fibonacci();
System.out.println(fibonacci.fib(2)); // Output: 1
System.out.println(fibonacci.fib(3)); // Output: 2
System.out.println(fibonacci.fib(4)); // Output: 3
}
}
When implementing memoization, it is important to avoid common mistakes such as:
Best practices for memoization include:
For more advanced use cases, memoization can be combined with other optimization techniques such as dynamic programming. In dynamic programming, we can use a bottom-up approach to compute the Fibonacci sequence iteratively, which can be more space-efficient than the top-down recursive approach.
Here is the complete code implementation of the memoized Fibonacci function in Java:
import java.util.HashMap;
import java.util.Map;
public class Fibonacci {
// Create a map to store the results of function calls
private Map<Integer, Integer> memo = new HashMap<>();
// Recursive function with memoization
public int fib(int n) {
// Base cases
if (n == 0) return 0;
if (n == 1) return 1;
// Check if the result is already computed
if (memo.containsKey(n)) {
return memo.get(n);
}
// Compute the result and store it in the map
int result = fib(n - 1) + fib(n - 2);
memo.put(n, result);
return result;
}
public static void main(String[] args) {
Fibonacci fibonacci = new Fibonacci();
System.out.println(fibonacci.fib(2)); // Output: 1
System.out.println(fibonacci.fib(3)); // Output: 2
System.out.println(fibonacci.fib(4)); // Output: 3
}
}
When debugging memoized functions, it is important to ensure that the data structure is being updated correctly and that the base cases are handled properly. Writing test cases for different inputs can help verify the correctness of the implementation.
Here are some test cases for the memoized Fibonacci function:
public class FibonacciTest {
public static void main(String[] args) {
Fibonacci fibonacci = new Fibonacci();
// Test cases
assert fibonacci.fib(0) == 0 : "Test case 0 failed";
assert fibonacci.fib(1) == 1 : "Test case 1 failed";
assert fibonacci.fib(2) == 1 : "Test case 2 failed";
assert fibonacci.fib(3) == 2 : "Test case 3 failed";
assert fibonacci.fib(4) == 3 : "Test case 4 failed";
assert fibonacci.fib(5) == 5 : "Test case 5 failed";
System.out.println("All test cases passed!");
}
}
When approaching problems related to memoization, it is helpful to:
Memoization is a valuable technique for optimizing recursive algorithms by storing and reusing the results of expensive function calls. By mastering memoization, you can significantly improve the efficiency of your code and tackle more complex problems with ease.
We encourage you to practice implementing memoization in different scenarios and explore further applications of this technique.
For further reading and practice problems related to memoization, check out the following resources: