Fibonacci Sequence (Dynamic Programming)
A classic problem solved using dynamic programming by storing results of subproblems.
Visualization
Details
Analogy
Imagine building a staircase. To know how to build the 10th step, you just need to look at the 8th and 9th steps you've already built. You don't need to re-measure from the ground up every time. Dynamic programming is like this: you solve bigger problems by using the solutions to the smaller problems you've already saved.
Purpose
To compute the nth Fibonacci number efficiently by building up from the base cases and storing intermediate results (memoization) to avoid redundant calculations.
Use Cases
Used in various algorithms for optimization, financial market analysis, and search algorithms. It's a foundational concept for learning dynamic programming.
Algorithm Steps
if n <= 1: return n
create array dp[0...n]
dp[0] = 0
dp[1] = 1
for i = 2 to n:
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
Explanation
What's Happening?
Initialize DP array. Base case: fib(0) = 0.
Code Implementation
def fibonacci(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]