Cheat Sheet

1-D DP Cheat Sheet

Quick reference for coding interviews. Bookmark this page!

What is 1-D DP?

Solve optimization problems with one-dimensional dynamic programming.

Trigger Words

When you see these in a problem, think 1-D DP:

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

Template Code

def climbStairs(n: int) -> int:
    if n <= 2:
        return n
    
    # Only need previous two values
    prev2, prev1 = 1, 2
    
    for i in range(3, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    
    return prev1

Complexity

Typical Time	`O(n)`
Typical Space	`O(1)`

Common Variations

Basic 1-D DP
1-D DP with constraints
Optimized 1-D DP

Practice Problems

Climbing Stairs easy Min Cost Climbing Stairs easy House Robber medium House Robber II medium Longest Palindromic Substring medium

See all 1-D DP problems →

Practice 1-D DP

Learn to recognize patterns instantly with interactive MCQs.

Download LeetEye Free