Pattern

1-D DP

Solve optimization problems with one-dimensional dynamic programming.

8 Problems

2 Easy

6 Medium

0 Hard

How 1-D DP Works

1D Dynamic Programming solves problems by storing solutions to subproblems in an array, where each entry depends only on previous entries. The pattern is: define state (what dp[i] represents), find the recurrence relation (how dp[i] relates to dp[i-1], dp[i-2], etc.), set base cases, and fill the array bottom-up. Classic examples include Fibonacci, climbing stairs, and house robber. Many 1D DP problems can be space-optimized to O(1) by only keeping the last few values.

When to Use 1-D DP

Pattern Recognition

Look for these trigger words in problem statements:

climbing stairs 1d-dp min cost climbing stairs house robber house robber ii longest palindromic substring palindromic substrings decode ways word break

Common Mistakes

Wrong state definition — dp[i] must have a clear, consistent meaning
Missing base cases (dp[0], dp[1] are often special)
Not considering all transitions — each dp[i] might depend on multiple previous states
Off-by-one errors in loop bounds when filling the DP table

When NOT to Use 1-D DP

When a greedy approach provably gives the optimal answer
When the problem doesn't have overlapping subproblems (use divide and conquer)
When the state space is too large to fit in memory

Practice Problems

Easy (2) Medium (6) Hard (0)

Climbing Stairs easy Min Cost Climbing Stairs easy House Robber medium House Robber II medium Longest Palindromic Substring medium Palindromic Substrings medium Decode Ways medium Word Break medium

Master 1-D DP

Build pattern recognition with interactive MCQs. Understand why to use 1-D DP, not just how.

Download LeetEye Free