Dynamic Programming is the most common pattern in LeetCode Medium/Hard problems. If you only learn one advanced technique, make it DP.

New to DP? The core idea is simple: break a big problem into smaller overlapping subproblems, solve each once, and reuse the results. That’s it. Everything else is details.

The DP Recipe (Use This Every Time)

Every DP problem follows the same four steps. Before writing any code, answer these questions on paper:

Step Question to Ask Example (House Robber)
1. Define state What does dp[i] represent? dp[i] = max money robbing houses 0..i
2. Transition How does dp[i] relate to smaller subproblems? dp[i] = max(dp[i-1], dp[i-2] + nums[i])
3. Base case What are the smallest subproblems I know the answer to? dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
4. Answer Which cell contains the final answer? dp[n-1]

How to Choose Which DP Type to Use

What does the problem ask? sequence / array grid / matrix choices / states 1D DP (Linear) 2D DP (Grid) State Machine DP subsequence? knapsack? LIS / Subsequence 0/1 Knapsack buy/sell games Stock Problems Bitmask DP Advanced Patterns (learn these after mastering the basics) Interval DP "merge / split ranges" Tree DP "DP on subtrees" Digit DP "count numbers ≤ N" DP + Bin Search "optimize O(n²) → O(n log n)" Quick Pattern Recognition "Maximum / minimum of something" → DP (optimization) "How many ways to..." → DP (counting) "Is it possible to..." → DP (feasibility) or greedy "Longest / shortest subsequence" → LIS-style DP "Path in a grid" → 2D DP

Contents

1D DP (Linear)

When to use: The problem involves a sequence (array, string) and asks for a maximum/minimum value or count. Each element either contributes to the answer or doesn’t.

The Pattern

dp[i] = best answer considering elements 0..i
dp[i] depends on dp[i-1], dp[i-2], ... (look back at previous states)

Example: House Robber (LC 198)

“Given an array of house values, find the max money you can rob without robbing two adjacent houses.”

Thinking through the recipe:

  1. State: dp[i] = max money from houses 0..i
  2. Transition: For house i, either skip it (dp[i-1]) or rob it (dp[i-2] + nums[i])
  3. Base: dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
  4. Answer: dp[n-1]
Houses: 2 7 9 3 1 dp[i]: 2 7 11 11 12 base max(2,7) max(7, 2+9) max(11, 7+3) max(11, 11+1) → Answer: 12 (rob houses 2, 9, 1) Transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) skip i rob i 
def knap01(wt: list[int], val: list[int], W: int) -> int:
    dp = [0] * (W + 1)
    for i in range(len(wt)):
        for w in range(W, wt[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
    return dp[W]

Template: 0/1 Knapsack

“Given items with weights and values, maximize total value without exceeding capacity W.”

The key insight: iterate items in the outer loop, capacity in reverse in the inner loop (to avoid using the same item twice).

def unique_paths_with_obstacles(g: list[list[int]]) -> int:
    m, n = len(g), len(g[0])
    if g[0][0] == 1:
        return 0
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1
    for i in range(m):
        for j in range(n):
            if g[i][j] == 1:
                dp[i][j] = 0
                continue
            if i > 0:
                dp[i][j] += dp[i - 1][j]
            if j > 0:
                dp[i][j] += dp[i][j - 1]
    return dp[m - 1][n - 1]
ID Title Link Solution
509 Fibonacci Number Link Solution
198 House Robber Link Solution
279 Perfect Squares Link Solution
322 Coin Change Link Solution
494 Target Sum Link Solution
139 Word Break Link -
487 Max Consecutive Ones II Link Solution
983 Minimum Cost For Tickets Link Solution
2466 Count Ways To Build Good Strings Link Solution
32 Longest Valid Parentheses Link Solution
91 Decode Ways Link Solution
416 Partition Equal Subset Sum Link Solution
918 Maximum Sum Circular Subarray Link Solution

2D DP (Grid)

When to use: The problem involves a 2D grid/matrix and asks about paths, areas, or values computed from neighboring cells.

The Pattern

dp[i][j] = answer for subproblem ending at cell (i, j)
dp[i][j] depends on dp[i-1][j] (above), dp[i][j-1] (left), dp[i-1][j-1] (diagonal)

Example: Unique Paths with Obstacles (LC 63)

“Count paths from top-left to bottom-right in a grid (can only move right or down). Some cells are blocked.”

Grid (0 = open, 1 = blocked): DP table (number of paths): 0 0 0 0 1 0 0 0 0 → 1 1 1 1 0 1 1 1 2 Answer = 2 How each cell is computed: if grid[i][j] == blocked: dp[i][j] = 0 else: dp[i][j] = dp[i-1][j] + dp[i][j-1] ↑ from above ↑ from left First row and column: dp = 1 (only one path to reach each edge cell) 
def length_of_lis(nums: list[int]) -> int:
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)
ID Title Link Solution
62 Unique Paths Link Solution
63 Unique Paths II Link Solution
64 Minimum Path Sum Link Solution
221 Maximal Square Link Solution
418 Sentence Screen Fitting Link Solution
568 Maximum Vacation Days Link Solution
96 Unique Binary Search Trees Link Solution

LIS (Longest Increasing Subsequence)

When to use: Find the longest subsequence where elements are in strictly increasing order. Also applies to problems reducible to LIS (Russian Doll Envelopes, etc.).

Visual Walkthrough

Array: 10 9 2 5 3 7 101 18 LIS = [2, 5, 7, 101] Length = 4 dp[i]: 1 1 1 2 2 3 4 4 dp[i] = length of longest increasing subsequence ending at index i O(n²) DP Approach For each i, look back at all j < i If nums[j] < nums[i]: dp[i] = max(dp[i], dp[j]+1) Simple but slow for n > 10⁴ Good enough for most LC problems O(n log n) Patience Sort Maintain a "tails" array of smallest tail elements Use binary search (lower_bound) to find position Fast enough for n up to 10⁵ Tails array length = LIS length (but NOT the LIS)

Template: O(n^2) DP

import bisect


def length_of_lis(nums: list[int]) -> int:
    tails: list[int] = []
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

Template: O(n log n) with Binary Search (Patience Sort)

def find_number_of_lis(nums: list[int]) -> int:
    n = len(nums)
    length = [1] * n
    count = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                if length[j] + 1 > length[i]:
                    length[i] = length[j] + 1
                    count[i] = count[j]
                elif length[j] + 1 == length[i]:
                    count[i] += count[j]
    max_len = max(length)
    return sum(c for l, c in zip(length, count) if l == max_len)

Template: Count Number of LIS (LC 673)

def interval_dp(arr: list[int]) -> int:
    n = len(arr)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = arr[i]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j])
    return dp[0][n - 1]
ID Title Link Solution
300 Longest Increasing Subsequence Link Solution
673 Number of Longest Increasing Subsequence Link Solution
354 Russian Doll Envelopes Link -
334 Increasing Triplet Subsequence Link -

Interval DP

When to use: The problem asks you to merge, split, or process contiguous ranges, and the optimal solution for a range depends on how you split it.

The pattern: Solve small intervals first, then build up to the full range by trying every possible split point.

dp[i][j] = best answer for the subarray from index i to j
For each split point k in [i, j):
    dp[i][j] = best(dp[i][k] + dp[k+1][j] + merge_cost)

Template

def max_coins(nums: list[int]) -> int:
    arr = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * (n + 2) for _ in range(n + 2)]
    for length in range(1, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            for k in range(i, j + 1):
                dp[i][j] = max(
                    dp[i][j],
                    dp[i][k - 1] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j + 1],
                )
    return dp[1][n]

Example: Burst Balloons (LC 312)

Think of it as: “which balloon do I burst last in the range [i, j]?”

def max_profit(prices: list[int]) -> int:
    hold, cash = -prices[0], 0
    for p in prices[1:]:
        hold = max(hold, cash - p)
        cash = max(cash, hold + p)
    return cash
ID Title Link Solution
312 Burst Balloons Link -
516 Longest Palindromic Subsequence Link -
1039 Minimum Score Triangulation of Polygon Link -
1130 Minimum Cost Tree From Leaf Values Link -

State Machine DP

When to use: The problem has distinct “modes” or “phases” where different rules apply. The classic example is the stock buy/sell family: at any moment, you’re either holding a stock or not.

The Key Idea

Instead of one DP array, maintain multiple arrays – one for each state. At each step, decide which state transitions are legal.

State Diagram: Stock Buy/Sell

Basic Buy/Sell (LC 122: unlimited transactions) Not Holding dp[i][1] Holding dp[i][0] buy (-price[i]) sell (+price[i]) wait wait With Cooldown (LC 309: must wait 1 day after selling) Rest (free) Holding Cooldown buy sell wait 1 day (cooldown → rest)

Template: Basic Buy/Sell (unlimited transactions)

def max_profit_cooldown(prices: list[int]) -> int:
    rest = 0
    hold = -prices[0]
    sold = float("-inf")
    for p in prices[1:]:
        rest, hold, sold = (
            max(rest, sold),
            max(hold, rest - p),
            hold + p,
        )
    return int(max(rest, sold))

Template: With Cooldown (3 states)

def rob(root) -> int:
    def dfs(node):
        if not node:
            return 0, 0
        left = dfs(node.left)
        right = dfs(node.right)
        not_take = max(left) + max(right)
        take = node.val + left[0] + right[0]
        return not_take, take

    return max(dfs(root))
ID Title Link Solution
121 Best Time to Buy and Sell Stock Link -
122 Best Time to Buy and Sell Stock II Link -
123 Best Time to Buy and Sell Stock III Link -
188 Best Time to Buy and Sell Stock IV Link -
309 Best Time to Buy and Sell Stock with Cooldown Link Solution
714 Best Time to Buy and Sell Stock with Transaction Fee Link -

DP on Trees

When to use: The problem asks for an optimal value on a tree structure. Each subtree is a subproblem, and you combine children’s results at each node.

The pattern: DFS returns DP values from leaves up. Each node returns a pair/tuple: {answer if we take this node, answer if we skip it}.

House Robber III: Can't rob parent + child 3 2 3 3 1 Option A: Rob root + leaves 3 + 3 + 1 = 7 (optimal) Option B: Rob middle level 2 + 3 = 5 = robbed = skipped

Template: Tree DP (House Robber III, LC 337)

def max_path_sum(root) -> int:
    best = float("-inf")

    def dfs(node):
        nonlocal best
        if not node:
            return 0
        left = max(0, dfs(node.left))
        right = max(0, dfs(node.right))
        best = max(best, node.val + left + right)
        return node.val + max(left, right)

    dfs(root)
    return best

Template: Max Path Sum (LC 124)

Each node contributes its value + best single path from one child. But the answer can also be a path through the node connecting both children.

def split_array(nums: list[int], m: int) -> int:
    def can_split(limit: int) -> bool:
        parts, cur = 1, 0
        for x in nums:
            if cur + x > limit:
                parts += 1
                cur = x
            else:
                cur += x
        return parts <= m

    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_split(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo
ID Title Link Solution
337 House Robber III Link -
124 Binary Tree Maximum Path Sum Link -
968 Binary Tree Cameras Link -

When to use: A pure DP solution is O(n^2) or worse, and binary search can help find the optimal transition in O(log n), bringing total time down.

Template: Binary Search on Answer (LC 410)

“Split array into m subarrays to minimize the largest subarray sum.”

The insight: binary search on the answer (the maximum sum), and use a greedy check.

from functools import lru_cache


def count_without_adjacent_equal_digits(N: int) -> int:
    s = str(N)

    @lru_cache(maxsize=None)
    def dfs(i: int, prev: int, tight: bool, started: bool) -> int:
        if i == len(s):
            return 1 if started else 0
        res = 0
        lim = int(s[i]) if tight else 9
        for d in range(lim + 1):
            nt = tight and d == lim
            ns = started or d != 0
            if not ns or prev == -1 or d != prev:
                res += dfs(i + 1, d if ns else prev, nt, ns)
        return res

    return dfs(0, -1, True, False)
ID Title Link Solution
300 Longest Increasing Subsequence Link Solution
410 Split Array Largest Sum Link -
875 Koko Eating Bananas Link -
1011 Capacity To Ship Packages Link -

Digit DP (count numbers with property)

When to use: “How many integers in [1, N] satisfy some digit-based property?” (e.g., no repeated digits, digit sum = k, etc.)

The pattern: Process digits left to right, tracking:

  • tight: are we still bounded by N’s digits?
  • started: have we placed a non-zero digit yet?
  • Any property-specific state (previous digit, digit sum, etc.)

Template

def tsp_min_cycle_cost(w: list[list[int]]) -> int:
    n = len(w)
    INF = 10**18
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0
    for mask in range(1, 1 << n):
        for u in range(n):
            if dp[mask][u] == INF:
                continue
            for v in range(n):
                if mask & (1 << v):
                    continue
                nm = mask | (1 << v)
                dp[nm][v] = min(dp[nm][v], dp[mask][u] + w[u][v])
    full = (1 << n) - 1
    return min(dp[full][u] + w[u][0] for u in range(n))
ID Title Link Solution
233 Number of Digit One Link -
902 Numbers At Most N Given Digit Set Link -
1012 Numbers With Repeated Digits Link -

Bitmask DP (TSP / subsets)

When to use: The problem has a small set of items (n le 20) and you need to track which items have been used. Each bit in a bitmask represents “used” (1) or “not used” (0).

The key constraint: n le 20 (otherwise 2^n states explode). If you see n le 15text{-}20 in the constraints, think bitmask.

Template: Traveling Salesman (TSP)

def tsp(w: list[list[int]]) -> int:
    n = len(w)
    INF = 10**9
    # dp[mask][u] = min cost to visit all nodes in mask, ending at u
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # start at node 0

    for mask in range(1, 1 << n):
        for u in range(n):
            if dp[mask][u] >= INF:
                continue
            for v in range(n):
                if mask & (1 << v):  # already visited
                    continue
                nxt = mask | (1 << v)
                dp[nxt][v] = min(dp[nxt][v], dp[mask][u] + w[u][v])
    return min(dp[-1])
ID Title Link Solution
847 Shortest Path Visiting All Nodes Link -
698 Partition to K Equal Sum Subsets Link -
1340 Jump Game V Link Solution
464 Can I Win Link -
691 Stickers to Spell Word Link -

Summary: When to Use Each DP Type

Type Signal in Problem Time Space
1D Linear Sequence, “rob/skip”, coin change O(n) or O(n × W) O(n) or O(W)
2D Grid Matrix, paths, grid traversal O(m × n) O(m × n)
LIS Longest increasing/decreasing subsequence O(n^2) or O(n log n) O(n)
State Machine Buy/sell, hold/not hold, cooldown O(n × k) O(n × k)
Interval Merge/split ranges, balloons, palindromes O(n^3) O(n^2)
Tree DP on subtrees, tree paths O(n) O(n)
Digit “Count numbers in [1, N] with property” O(text{digits} × text{states}) Same
Bitmask Small n (le 20), subset selection O(2^n × n) O(2^n × n)

More Templates