Build solutions bottom-up using a 1D array. Identify the recurrence: dp[i] depends on dp[i-1], dp[i-2], or a range. Recognize classic patterns: Fibonacci, knapsack, LIS.
Problems: 12
Easy: 2
Medium: 10
Hard: 0
Learning approach: Read the problem. Try the test cases yourself first.
Click Hint if stuck — it guides without spoiling.
Use Show Solution only after a genuine attempt.
Then hit Let's Code to run your solution live.
To reach step n, you came from step n-1 or step n-2. climbStairs(n) = climbStairs(n-1) + climbStairs(n-2).
Python Solution
def climbStairs(n):
# dp[i] = ways to reach step i = dp[i-1] + dp[i-2]
a, b = 1, 1 # a = dp[i-2], b = dp[i-1]
for _ in range(n - 1):
a, b = b, a + b
return b
Key idea: Classic Fibonacci. The number of ways to reach step n is the sum of ways to reach n-1 and n-2. Optimize space by rolling just two variables.
Each step has a cost. You can start at step 0 or 1. At each step, you can climb 1 or 2 steps. Find minimum cost to reach the top (beyond the last step).
dp[i] = cost[i] + min(dp[i-1], dp[i-2]). The answer is min(dp[-1], dp[-2]) — you can take the last 1 or 2 steps from the end.
Python Solution
def minCostClimbingStairs(cost):
n = len(cost)
dp = cost[:]
for i in range(2, n):
dp[i] += min(dp[i-1], dp[i-2])
return min(dp[-1], dp[-2])
Key idea: dp[i] stores the total cost to reach and leave step i. For each step, add the cheaper of the two approaches. Answer is the min of the last two (since you can reach the top from either).
Rob houses along a street. Adjacent houses have alarms — can't rob two consecutive houses. Maximize the total amount robbed.
Test Cases
rob([1,2,3,1]) → 4
rob([2,7,9,3,1]) → 12
skip/take DProlling two varsO(n) O(1)
At each house, either rob it (prev2 + current) or skip it (prev1). dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
Python Solution
def rob(nums):
prev2 = prev1 = 0
for n in nums:
prev2, prev1 = prev1, max(prev1, prev2 + n)
return prev1
Key idea: Classic skip/take DP. Keep track of the best result using 1 house and 2 houses back. For each house: either skip it (keep prev1) or rob it (prev2 + n).
Either you rob the first house (can't rob the last) or you don't (can try the last). Run linear House Robber on two subarrays: nums[0:-1] and nums[1:].
Python Solution
def rob(nums):
if len(nums) == 1:
return nums[0]
def rob_linear(arr):
prev2 = prev1 = 0
for n in arr:
prev2, prev1 = prev1, max(prev1, prev2 + n)
return prev1
return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))
Key idea: Break the circle by running House Robber I twice: once excluding the last house, once excluding the first. Take the maximum.
Given string s, return the longest palindromic substring.
Test Cases
longestPalindrome('babad') → 'bab' or 'aba'
longestPalindrome('cbbd') → 'bb'
expand around centerodd/even centerO(n²)
For each character (and gap between characters), try expanding outward as long as characters match. Track the longest expansion found.
Python Solution
def longestPalindrome(s):
result = ""
for i in range(len(s)):
# Odd length palindromes (center at i)
for left, right in [(i, i), (i, i+1)]:
while left >= 0 and right < len(s) and s[left] == s[right]:
if right - left + 1 > len(result):
result = s[left:right+1]
left -= 1
right += 1
return result
Key idea: Expand around each character as center. Try both odd centers (single char) and even centers (pair of chars). Track the longest palindrome found.
Expand around each center. Every successful expansion (s[left]==s[right]) is one palindrome. Count all of them.
Python Solution
def countSubstrings(s):
count = 0
for i in range(len(s)):
for left, right in [(i, i), (i, i + 1)]:
while left >= 0 and right < len(s) and s[left] == s[right]:
count += 1
left -= 1
right += 1
return count
Key idea: Same expansion trick as Longest Palindromic Substring, but instead of tracking the longest, count every valid expansion.
dp[i] = ways to decode s[0:i]. At each position, try using 1 digit (if not '0') and 2 digits (if 10-26). Sum valid cases.
Python Solution
def numDecodings(s):
if s[0] == '0':
return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1 # empty string — one way
dp[1] = 1 # first character (already checked it's not '0')
for i in range(2, n + 1):
if s[i-1] != '0': # use one digit
dp[i] += dp[i-1]
two_digit = int(s[i-2:i])
if 10 <= two_digit <= 26: # use two digits
dp[i] += dp[i-2]
return dp[n]
Key idea: dp[i] = number of ways to decode first i characters. Two choices: use the last 1 digit (valid if not '0'), or use the last 2 digits (valid if 10-26). Sum valid options.
Track both the current max and min product at each position (negatives flip the sign). Reset on zero.
Python Solution
def maxProduct(nums):
result = max(nums)
cur_min = cur_max = 1
for n in nums:
if n == 0:
cur_min = cur_max = 1
continue
candidates = (n * cur_max, n * cur_min, n)
cur_max = max(candidates)
cur_min = min(candidates)
result = max(result, cur_max)
return result
Key idea: Track both maximum and minimum running products. A negative number flips max↔min. Zeros reset both. At each step, consider: extend max, extend min, or restart with just n.
dp[i] = True if s[0:i] can be segmented. For each i, try all j < i: if dp[j] and s[j:i] is a word, dp[i] = True.
Python Solution
def wordBreak(s, wordDict):
word_set = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True # empty string is always valid
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[len(s)]
Key idea: dp[i] tells us if s[0:i] is breakable. For each position i, check all sub-strings s[j:i]. If s[0:j] is breakable (dp[j]) and s[j:i] is in the dictionary, then s[0:i] is breakable.
Time: O(n²·m) — n² substrings, m=max word length. Space: O(n).
Maintain a list 'tails' where tails[i] is the smallest tail element for all increasing subsequences of length i+1. Binary search to update.
Python Solution
import bisect
def lengthOfLIS(nums):
tails = [] # tails[i] = smallest tail of increasing subsequence of length i+1
for n in nums:
pos = bisect.bisect_left(tails, n)
if pos == len(tails):
tails.append(n) # extend the longest sequence
else:
tails[pos] = n # replace to keep tails as small as possible
return len(tails)
Key idea: Patience sort. tails is always sorted. Binary search to find where to place each number. If it extends beyond all tails, append. Otherwise replace to keep tails minimal (enabling longer sequences later).
Given integer array nums, return True if it can be partitioned into two subsets with equal sum.
Test Cases
canPartition([1,5,11,5]) → True # [1,5,5] and [11]
canPartition([1,2,3,5]) → False
0/1 knapsackset of reachable sumsO(n·sum)
If total sum is odd, impossible. Otherwise, find if there's a subset summing to total/2. Use a set of reachable sums.
Python Solution
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = {0} # set of reachable sums
for n in nums:
dp = dp | {s + n for s in dp}
if target in dp:
return True
return False
Key idea: 0/1 knapsack: can we reach a sum of total/2? Maintain a set of all achievable sums. For each number, add it to all existing sums. Early exit if target is reached.