BeginnerDynamic Programming

1D DP

Linear DP over arrays or sequences: Kadane, House Robber, Stocks, LIS

Time: O(n)
Space: O(1)–O(n)
Pattern Overview

Core Idea

dp[i] summarizes optimal value up to i using transitions from previous states.

When to Use

Use when the subproblem depends on a fixed number of previous positions.

General Recognition Cues
General indicators that this pattern might be applicable
  • Max subarray
  • Robbing non-adjacent
  • Profit with cooldown
  • LIS
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

Kadane

Max subarray ending at i

When to Use This Variant
  • Running best
Use Case
Max sum
Advantages
  • O(n)
  • O(1) space
Implementation
def kadane(nums):
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best
2

House Robber

dp[i]=max(dp[i-1],dp[i-2]+val)

When to Use This Variant
  • Non-adjacent
Use Case
Max loot
Advantages
  • O(n)
  • O(1) space w/ roll
Implementation
def house_robber(nums):
    prev2 = 0; prev1 = 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1
3

Stocks

State machine for buy/sell/cooldown

When to Use This Variant
  • Transactions
Use Case
Profit max
Advantages
  • Clear transitions
Implementation
def max_profit_one_tx(prices):
    minp = float('inf'); best = 0
    for p in prices:
        minp = min(minp, p); best = max(best, p - minp)
    return best
4

LIS

n log n with tails or O(n^2) DP

When to Use This Variant
  • Increasing
Use Case
Subsequence length
Advantages
  • Efficient with binary search
Implementation
from bisect import bisect_left
def lis_length(nums):
    tails=[]
    for x in nums:
        i=bisect_left(tails, x)
        if i==len(tails): tails.append(x)
        else: tails[i]=x
    return len(tails)
Common Pitfalls
Watch out for these common mistakes
  • Wrong base cases
  • Transition off-by-one
  • Overwriting needed state
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(n)

Linear or n log n for LIS.

Space Complexity
O(1)–O(n)

Rolling vars or arrays.

Ready to test your knowledge?

Test your pattern recognition with interactive questions