About This Pattern
Master the Dynamic Programming (1D) pattern by practicing these problems organized by difficulty.Focus on the Key Signals - these are the indicators that tell you when to use this pattern.
Easy (2)
Climbing Stairs
Count distinct ways to climb n stairs (1 or 2 steps at a time).
Key Signals:
Fibonacci-likedp[i] = dp[i-1] + dp[i-2]Count ways
Min Cost Climbing Stairs
Find minimum cost to reach top of stairs with given costs per step.
Key Signals:
Minimize costChoice of starting stepdp[i] = cost[i] + min(dp[i-1], dp[i-2])
Medium (3)
House Robber
Maximize money robbed from houses without robbing adjacent houses.
Key Signals:
Cannot take adjacentMax of take or skipdp[i] = max(dp[i-1], dp[i-2] + nums[i])
Decode Ways
Count ways to decode a string of digits where A=1, B=2, ..., Z=26.
Key Signals:
Count decodingsSingle or two digit choicesHandle zeros carefully
Word Break
Determine if string can be segmented into dictionary words.
Key Signals:
Boolean DPCheck all substringsdp[i] = any(dp[j] && s[j:i] in dict)