LeetCode · DP — 1D
Dynamic Programming — 1D Problem Set
Single-dimension DP: dp[i] depends on previous states. Start with simple recurrence, then optimise space.
Concept page: Dynamic Programming
| Difficulty | Pattern | Problem | Key Insight |
|---|---|---|---|
| Easy | fibonacci | LC 70 · Climbing Stairs | dp[i] = dp[i-1] + dp[i-2]. O(n) time, O(1) space. |
| Medium | take/skip | LC 198 · House Robber | dp[i] = max(dp[i-1], dp[i-2] + nums[i]). O(n). |
| Medium | circular | LC 213 · House Robber II | Two passes: [0..n-2] and [1..n-1], take max. O(n). |
| Medium | decode | LC 91 · Decode Ways | dp[i] = dp[i-1] (single digit valid) + dp[i-2] (two digits valid). O(n). |
| Medium | unbounded | LC 322 · Coin Change | dp[amount] = min coins. Unbounded knapsack variant. O(n·amount). |
| Medium | product | LC 152 · Maximum Product Subarray | Track max and min (negatives flip). O(n). |
| Medium | word-break | LC 139 · Word Break | dp[i] = can s[0..i] be segmented? Try all prefixes in dictionary. O(n·m). |
| Medium | LIS | LC 300 · Longest Increasing Subsequence | O(n²) DP or O(n log n) with patience sorting. |
| Medium | palindrome | LC 647 · Palindromic Substrings | Expand around each center. O(n²). |