aloalgo.com1D Dynamic Programming
1D DP problems have a state that depends on a single variable. In this chapter, we'll explore the tabulation (bottom-up) approach and see how it compares to memoization.Tabulation: Bottom-Up DP
While memoization works top-down (starting from the answer and recursing down), tabulation works bottom-up: we build answers starting from the smallest subproblems.- Iterative (no recursion)
- Build answers from smallest subproblems upward
- Uses arrays to store results
Example: Fibonacci with Tabulation
- F - Function:
dp[i]= ith Fibonacci number - A - Arguments: index
i - S - Transition:
dp[i] = dp[i-1] + dp[i-2] - T - Termination:
dp[0] = 0,dp[1] = 1
Table Diagram
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| dp[n] | 0 | 1 | 1 | 2 | 3 | 5 | 8 |
Memoization vs Tabulation
| Memoization (Top-Down) | Tabulation (Bottom-Up) | |
|---|---|---|
| Approach | Recursive with caching | Iterative with array |
| Pros | Easier to write, only computes needed states | No recursion limits, easier to optimize space |
| Cons | Stack overflow risk, function call overhead | Must compute all states, harder to derive |
| Best for | Interviews, sparse state spaces | Production, space optimization |
Example: House Robber
Problem: Given an array of house values, find the maximum amount you can rob without robbing adjacent houses.- F - Function:
dp[i]= max money robbing houses 0 to i - A - Arguments: index
i - S - Transition:
dp[i] = max(dp[i-1], dp[i-2] + nums[i]) - T - Termination:
dp[0] = nums[0],dp[1] = max(nums[0], nums[1])
Example: Coin Change (Minimum Coins)
Problem: Given coin denominations and a target amount, find the minimum number of coins needed.- F - Function:
dp[i]= min coins to make amount i - A - Arguments: amount
i - S - Transition:
dp[i] = min(dp[i - coin] + 1)for each coin - T - Termination:
dp[0] = 0
Recognizing 1D DP Problems
Pattern: 1D DP is used when the state depends on a single variable (usually an index or amount).Common 1D DP problems:
- Fibonacci and variants
- Climbing stairs
- House robber
- Coin change
- Maximum subarray sum
- Decode ways
dp[i] only depends on previous indices like dp[i-1], dp[i-2], etc., it's 1D DP.Practice Problems
Next Steps
Ready for more complexity? Continue to 2D Dynamic Programming to tackle grid problems, string DP, and more.Was this helpful?
Company
Practice
Learn
© 2026 aloalgo.com. All rights reserved.