NeetCode 150 · 1D Dynamic Programming

1D Dynamic Programming Problems

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.
01 Easy MathDPMemoization
You can climb 1 or 2 steps at a time. Given n steps, how many distinct ways to reach the top?
Test Cases
climbStairs(2) → 2 # [1+1, 2] climbStairs(3) → 3 # [1+1+1, 1+2, 2+1] climbStairs(5) → 8
FibonacciO(n) O(1)rolling variables
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.
Time: O(n).
Space: O(1).
02 Easy ArrayDP
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).
Test Cases
minCostClimbingStairs([10,15,20]) → 15 minCostClimbingStairs([1,100,1,1,1,100,1,1,100,1]) → 6
dp[i] += min(dp[i-1],dp[i-2])O(n) O(1)
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).
Time: O(n).
Space: O(n).
03 Medium ArrayDP
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).
Time: O(n).
Space: O(1).
04 Medium ArrayDP
Houses are in a circle. First and last houses are adjacent. Find max rob amount.
Test Cases
rob([2,3,2]) → 3 rob([1,2,3,1]) → 4 rob([1,2,3]) → 3
two linear rob callsskip first or lastO(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.
Time: O(n).
Space: O(1).
05 Medium StringDP
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.
Time: O(n²).
Space: O(1).
06 Medium StringDP
Given string s, return the number of palindromic substrings.
Test Cases
countSubstrings('abc') → 3 # 'a','b','c' countSubstrings('aaa') → 6 # 'a','a','a','aa','aa','aaa'
expand around centercount all expansionsO(n²)
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.
Time: O(n²).
Space: O(1).
07 Medium StringDP
String of digits can be decoded: '1'→'A', '2'→'B', ..., '26'→'Z'. Return number of ways to decode string s.
Test Cases
numDecodings('12') → 2 # 'AB' or 'L' numDecodings('226') → 3 # 'BZ','VF','BBF' numDecodings('06') → 0
single-digit decodetwo-digit decodedp O(n)
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.
Time: O(n).
Space: O(n).
08 Medium ArrayDPBFS
Given coin denominations and an amount, find the minimum number of coins to make up that amount. Return -1 if impossible.
Test Cases
coinChange([1,5,6,9], 11) → 2 # 5+6 coinChange([2], 3) → -1 coinChange([1,2,5], 11) → 3 # 5+5+1
bottom-up unbounded knapsackdp[0]=0O(amount·coins)
dp[i] = min coins for amount i. For each amount, try each coin: dp[i] = min(dp[i], dp[i-coin]+1).
Python Solution
def coinChange(coins, amount): dp = [float('inf')] * (amount + 1) dp[0] = 0 # 0 coins needed for amount 0 for i in range(1, amount + 1): for coin in coins: if coin <= i: dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] != float('inf') else -1
Key idea: Classic DP. Build up from 0 to amount. For each amount, try every coin and take the minimum. Initialize all to infinity except dp[0]=0.
Time: O(amount · coins).
Space: O(amount).
09 Medium ArrayDP
Find the contiguous subarray with the largest product.
Test Cases
maxProduct([2,3,-2,4]) → 6 # [2,3] maxProduct([-2,0,-1]) → 0
track cur_max and cur_minhandle negativesO(n)
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.
Time: O(n).
Space: O(1).
10 Medium ArrayHash TableDPTrie
Given string s and dictionary of strings, return True if s can be segmented into space-separated dictionary words.
Test Cases
wordBreak('leetcode', ['leet','code']) → True wordBreak('applepenapple', ['apple','pen']) → True wordBreak('catsandog', ['cats','dog','sand','and','cat']) → False
dp boolean arrayword_set for O(1) lookupO(n²·m)
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).
11 Medium ArrayDPBinary Search
Given integer array nums, return the length of the longest strictly increasing subsequence.
Test Cases
lengthOfLIS([10,9,2,5,3,7,101,18]) → 4 # [2,3,7,18] lengthOfLIS([0,1,0,3,2,3]) → 4
patience sortbisect_leftO(n log 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).
Time: O(n log n).
Space: O(n).
12 Medium ArrayDP
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.
Time: O(n·sum).
Space: O(sum).
← Prev Category Next Category →