← DSADSA 5.1
DP Foundations (1D)
Not started yet — 7 problems queued, opening the deepest phase of the roadmap.
Identify overlapping subproblems plus optimal substructure; define the state, the recurrence, and the base case, then choose top-down (memoized recursion) or bottom-up (tabulation). Start with "decision at each step" problems before layering on more state.
Sub-patterns
- A — Linear 1D DP. State depends only on a fixed number of previous positions.
- B — Take/Skip Decision DP. At each step, decide to take the current element or skip it.
- C — Space-Optimized DP. Collapse the DP array down to a few rolling variables.
Practice set (7)
- Easy — Climbing Stairs, Min Cost Climbing Stairs
- Medium — House Robber, House Robber II, Decode Ways, Perfect Squares, Maximum Subarray
Pending
Linear 1D DP
State depends only on a fixed number of previous positions — the simplest DP shape.
Pending
Take/Skip Decision DP
At each step, decide whether to take the current element or skip it, keeping the better of the two.
Pending
Space-Optimized DP
Collapse the full DP array down to a few rolling variables once the recurrence only looks back a fixed distance.
Notes from readers
Comments — via GitHub