The Fibonacci sequence is a classic problem we often encounter in programming. Its definition is simple: the 0th term is 0, the 1st term is 1, and starting from the 2nd term, each term is the sum of the two preceding terms. Mathematically, this is expressed as: f(0) = 0, f(1) = 1, and for n > 1, f(n) = f(n-1) + f(n-2).
To calculate f(5), we can do it step by step: f(2) = f(1) + f(0) = 1 + 0 = 1, f(3) = f(2) + f(1) = 1 + 1 = 2, f(4) = f(3) + f(2) = 2 + 1 = 3, f(5) = f(4) + f(3) = 3 + 2 = 5. This process seems straightforward, but what happens when n becomes very large, such as n = 100?
Problems with the Brute-force Recursive Approach¶
Let’s first try the simplest recursive method:
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
The issue with this method is excessive repeated calculations. For example, when calculating f(5), fib(3) is computed twice and fib(2) three times. As n increases, the number of repeated calculations grows exponentially, resulting in a time complexity of O(2^n), making it nearly unusable.
Core Idea of Dynamic Programming¶
The core of dynamic programming is “remembering the answers to solved subproblems to avoid redundant calculations”. It’s like when solving a math problem, if you’ve already computed a step, you directly use the result instead of recalculating from scratch.
1. Memoization Recursion (with a Memo)¶
We can use an array (memo) to store the computed Fibonacci numbers. When calculating f(n), first check if the result is already in the memo. If yes, return it immediately; if not, compute it and store it in the memo.
Code implementation:
int fib(int n) {
if (n <= 1) return n;
vector<int> memo(n + 1, -1); // Memo array, initialized to -1 (uncomputed)
return helper(n, memo);
}
int helper(int n, vector<int>& memo) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n]; // If computed, return directly
memo[n] = helper(n - 1, memo) + helper(n - 2, memo); // Compute and store
return memo[n];
}
In this method, each f(k) is computed only once. The time complexity is O(n), and the space complexity is O(n) (due to the memo array).
2. Iterative Approach (Bottom-up)¶
A more efficient approach is iteration. Since each Fibonacci term only depends on the two preceding terms, we can use two variables to track the values of the previous two terms and iteratively compute the next term, eliminating the need for an extra array.
Code implementation:
int fib(int n) {
if (n <= 1) return n;
int a = 0; // f(0)
int b = 1; // f(1)
for (int i = 2; i <= n; ++i) {
int c = a + b; // Compute current term
a = b; // Update previous term
b = c; // Update current term
}
return b;
}
This method has a time complexity of O(n) and a space complexity of O(1), making it the optimal solution.
Key Characteristics of Dynamic Programming¶
Through the Fibonacci sequence, we can understand two core properties of dynamic programming:
1. Overlapping Subproblems: A large problem decomposes into smaller subproblems, and smaller subproblems are recalculated multiple times (e.g., f(3) is needed when calculating both f(5) and f(4)).
2. Optimal Substructure: The solution to the current problem depends on the solutions to its subproblems (f(n) = f(n-1) + f(n-2)).
Summary¶
The essence of dynamic programming is trading space for time by storing subproblem results to avoid redundant calculations. The Fibonacci sequence is a classic introductory case for dynamic programming. From brute-force recursion to memoization recursion and finally to the iterative method, each step reflects an optimization idea. Mastering this method allows you to solve more complex problems, such as climbing stairs or the longest common subsequence.
Start applying dynamic programming to solve more practical problems now!