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 
int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];

    vector<int> dp(n);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);

    for (int i = 2; i < n; ++i)
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);

    return dp[n - 1];
}

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).

int knapsack01(vector<int>& wt, vector<int>& val, int W) {
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < (int)wt.size(); ++i)
        for (int w = W; w >= wt[i]; --w)
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
    return dp[W];
}
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) 
int uniquePathsWithObstacles(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    if (grid[0][0] == 1) return 0;

    vector<vector<int>> dp(m, vector<int>(n, 0));
    dp[0][0] = 1;

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[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
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

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);

    for (int i = 1; i < n; ++i)
        for (int j = 0; j < i; ++j)
            if (nums[j] < nums[i])
                dp[i] = max(dp[i], dp[j] + 1);

    return *max_element(dp.begin(), dp.end());
}

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

int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) tails.push_back(num);
        else *it = num;
    }
    return tails.size();
}

Template: Count Number of LIS (LC 673)

int findNumberOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> length(n, 1), count(n, 1);

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[j] < nums[i]) {
                if (length[j] + 1 > length[i]) {
                    length[i] = length[j] + 1;
                    count[i] = count[j];
                } else if (length[j] + 1 == length[i]) {
                    count[i] += count[j];
                }
            }
        }
    }

    int maxLen = *max_element(length.begin(), length.end());
    int result = 0;
    for (int i = 0; i < n; ++i)
        if (length[i] == maxLen) result += count[i];
    return result;
}
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

int intervalDP(vector<int>& arr) {
    int n = arr.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));

    for (int i = 0; i < n; ++i) dp[i][i] = arr[i]; // base: length 1

    for (int len = 2; len <= n; ++len) {
        for (int i = 0; i <= n - len; ++i) {
            int j = i + len - 1;
            for (int k = i; k < j; ++k)
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + cost(i, k, j));
        }
    }
    return dp[0][n - 1];
}

Example: Burst Balloons (LC 312)

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

int maxCoins(vector<int>& nums) {
    int n = nums.size();
    vector<int> arr = {1};
    arr.insert(arr.end(), nums.begin(), nums.end());
    arr.push_back(1);

    vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
    for (int len = 1; len <= n; ++len) {
        for (int i = 1; i <= n - len + 1; ++i) {
            int j = i + len - 1;
            for (int k = i; k <= j; ++k)
                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];
}
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)

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    vector<vector<int>> dp(n, vector<int>(2, 0));

    dp[0][0] = -prices[0];  // holding: bought on day 0
    dp[0][1] = 0;            // not holding: did nothing

    for (int i = 1; i < n; ++i) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // hold or buy
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]); // rest or sell
    }
    return dp[n - 1][1];
}

Template: With Cooldown (3 states)

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    vector<vector<int>> dp(n, vector<int>(3, 0));

    dp[0][0] = 0;            // rest
    dp[0][1] = -prices[0];   // hold
    dp[0][2] = INT_MIN;      // sold (impossible on day 0)

    for (int i = 1; i < n; ++i) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][2]);              // rest or cooldown done
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);  // hold or buy
        dp[i][2] = dp[i - 1][1] + prices[i];                      // sell
    }
    return max(dp[n - 1][0], dp[n - 1][2]);
}
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)

pair<int, int> dfs(TreeNode* root) {
    if (!root) return {0, 0};

    auto left = dfs(root->left);
    auto right = dfs(root->right);

    int skip = max(left.first, left.second) + max(right.first, right.second);
    int take = root->val + left.first + right.first;

    return {skip, take};  // {not take, take}
}

int rob(TreeNode* root) {
    auto [skip, take] = dfs(root);
    return max(skip, take);
}

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.

int maxPathSum(TreeNode* root) {
    int maxSum = INT_MIN;

    function<int(TreeNode*)> dfs = [&](TreeNode* node) -> int {
        if (!node) return 0;
        int left = max(0, dfs(node->left));
        int right = max(0, dfs(node->right));
        maxSum = max(maxSum, node->val + left + right); // path through node
        return node->val + max(left, right);             // best single path up
    };

    dfs(root);
    return maxSum;
}
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.

bool canSplit(vector<int>& nums, int m, int maxSum) {
    int count = 1, sum = 0;
    for (int num : nums) {
        if (sum + num > maxSum) { ++count; sum = num; }
        else sum += num;
    }
    return count <= m;
}

int splitArray(vector<int>& nums, int m) {
    int lo = *max_element(nums.begin(), nums.end());
    int hi = accumulate(nums.begin(), nums.end(), 0);

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canSplit(nums, m, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
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

string sN;
long long dp[20][11][2][2];

long long dfs(int i, int prev, bool tight, bool started) {
    if (i == (int)sN.size()) return started ? 1 : 0;
    auto& res = dp[i][prev + 1][tight][started];
    if (res != -1) return res;
    res = 0;

    int limit = tight ? (sN[i] - '0') : 9;
    for (int d = 0; d <= limit; ++d) {
        bool nt = tight && (d == limit);
        bool ns = started || (d != 0);
        if (!ns || prev == -1 || d != prev) // example: no consecutive same digits
            res += dfs(i + 1, ns ? d : prev, nt, ns);
    }
    return res;
}

long long solve(long long N) {
    sN = to_string(N);
    memset(dp, -1, sizeof dp);
    return dfs(0, -1, true, false);
}
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)

int tsp(const vector<vector<int>>& w) {
    int n = w.size();
    const int INF = 1e9;
    // dp[mask][u] = min cost to visit all nodes in mask, ending at u
    vector<vector<int>> dp(1 << n, vector<int>(n, INF));
    dp[1][0] = 0; // start at node 0

    for (int mask = 1; mask < (1 << n); ++mask) {
        for (int u = 0; u < n; ++u) {
            if (dp[mask][u] >= INF) continue;
            for (int v = 0; v < n; ++v) {
                if (mask & (1 << v)) continue; // already visited
                int next = mask | (1 << v);
                dp[next][v] = min(dp[next][v], dp[mask][u] + w[u][v]);
            }
        }
    }
    return *min_element(dp.back().begin(), dp.back().end());
}
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