54. DP Example 2: Tabulation (Bottom-Up Approach)

Tabulation is a bottom-up dynamic programming technique. Instead of starting from the desired solution (N) and recursively breaking it down, we start from the base case (0 or 1) and iteratively build up the solution using loops.

Fibonacci Sequence Example (Tabulated)

1. Initialize a table (array) to store solutions for subproblems, usually up to the target N.
2. Fill in the base cases (e.g., dp[0]=0, dp[1]=1).
3. Iteratively calculate the remaining values based on the stored previous values.

python def fib_tabulation(n): if n <= 1: return n

dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1

# Iteratively build up the results
for i in range(2, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]
    
return dp[n]

Tabulation often avoids the function call overhead of recursion, sometimes offering a small speed advantage over memoization.