1D DP
Define dp[i] as the answer for the prefix ending at i, then write the recurrence from a constant number of earlier states.
Dynamic ProgrammingO(n) time, often O(1) space after optimisationNew19 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
climbing stairs
house robber
decode ways
jump game
The template
Get this into muscle memory, then adapt the condition per problem.
const dp = new Array(n + 1).fill(0); dp[0] = base0; dp[1] = base1; for (let i = 2; i <= n; i++) dp[i] = combine(dp[i - 1], dp[i - 2], a[i]); return dp[n];Watch Memoisation vs Brute Force
If you are stuck
The generic hint ladder for this pattern, in order.
- 1What is the answer for the first i elements, given the answers before it?
- 2List the choices at position i and take the best one.
- 3If only the last two states are read, two variables are enough.
Drill it
Every problem in the bank that uses this pattern.
0 / 19 solved