Pattern 07 of 08 · dp-1d
1D Dynamic Programming
Decompose optimization problems into overlapping subproblems with optimal substructure, caching intermediate transition states in linear memory.
- Builds on
- Backtracking & Decision Trees
- Unlocks
- The end of this branch.
See the invariant
Step through itdp-1dInteractive Sandbox
Curated visualizer for dp-1d is available via Socratic AI Mentor steps and the interactive playground below.
Pattern InvariantTwo Pointers
Converging search on sorted array: Target Sum = 26
Step 1 of 3
L
2
[0]7
[1]11
[2]15
[3]19
[4]R
23
[5]nums[0] (2)+nums[5] (23)=25<Target (26)
Sum 25 < target (26). Since array is sorted, we MUST increase left pointer (L: 0 to 1) to seek a larger sum.
Speed: