← All patterns1D Dynamic Programming · template
Pattern · Dynamic Programming
1D Dynamic Programming
Define dp[i] as the answer for the first i items, write how it depends on smaller i, and fill it left to right.
Time O(n) · Space O(n), often O(1) with two variables
Taught in Module 28: DP Foundations: 1D
Think of it like this
Climbing stairs and writing on each step how many ways there are to reach it: each number comes from the one or two steps below.
Clues that point here
- → Count the ways
- → Maximum or minimum over choices at each step
- → "You can't take two adjacent"
- → Recursion with repeated subproblems
Not this pattern when
- ✕ Choices interact across far-apart positions (2D or interval DP)
- ✕ A greedy choice is provably safe
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
int[] dp = new int[n + 1];
dp[0] = base0; dp[1] = base1;
for (int i = 2; i <= n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + value[i - 1]); // the recurrence
}
return dp[n];Common versions
- Climbing stairs
- House robber
- Decode ways
- Min cost climbing stairs
- Word break
Practice problems with this pattern
28.1Climbing StairsEasymain pattern28.2Min Cost Climbing StairsEasymain pattern28.3House RobberMediummain pattern28.4House Robber IIMediummain pattern28.5Delete and EarnMediummain pattern28.6Decode WaysMediummain pattern28.7Word BreakMediummain pattern28.8Maximum Product SubarrayMediummain pattern32.1Best Time to Buy and Sell Stock with CooldownMediummain pattern32.2Best Time to Buy and Sell Stock with Transaction FeeMediummain pattern32.3Best Time to Buy and Sell Stock IVHardmain pattern12.1Fibonacci NumberEasyalso uses it24.4Parallel Courses IIIHardalso uses it26.3Cheapest Flights Within K StopsMediumalso uses it26.7Number of Ways to Arrive at DestinationMediumalso uses it32.6House Robber IIIMediumalso uses it33.2Jump GameMediumalso uses it33.9Best Time to Buy and Sell Stock IIMediumalso uses it34.3Counting BitsEasyalso uses it