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

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

Contents

1D DP (knapsack/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

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

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

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

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]

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

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]

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

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]

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

static int knap01(int[] wt, int[] val, int W){
    int[] dp = new int[W + 1];
    for (int i=0;i<wt.length;++i)
        for (int w=W; w>=wt[i]; --w)
            dp[w] = Math.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/path)

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

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

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

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

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

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 
static int uniquePaths(int[][] g){
    int m=g.length, n=g[0].length;
    int[][] dp = new int[m][n];
    if (g[0][0]==1) return 0; dp[0][0]=1;
    for (int i=0;i<m;++i) for(int j=0;j<n;++j){
        if (g[i][j]==1){ dp[i][j]=0; continue; }
        if (i) dp[i][j]+=dp[i-1][j];
        if (j) 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

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

Template: Count Number of LIS (LC 673)

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 - 
static int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];

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

    return max_element = new return(dp /* elements of dp */);
}

static int lengthOfLIS(int[] nums) {
    List<Integer> tails = new ArrayList<>();

    for (int num : nums) {
        var it = floorKey(tails /* elements of tails */, num);
        if (it == tails.iterator()) {
            tails.add(num);
        } else {
            *it = num;
        }
    }

    return tails.size();
}

Count Number of LIS

// import java.util.Arrays;
// import java.util.Collections;
static int findNumberOfLIS(int[] nums) {
    int n = nums.length;
    int[] length = new int[n], 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.put(i, count.getOrDefault(i, 0) + count[j];
                }
            }
        }
    }

    int maxLen = Arrays.stream(length).Math.max().getAsInt();
    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

Example: Burst Balloons (LC 312)

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

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

Example: Burst Balloons (LC 312)

Think of it as: “which balloon do I burst last in the range [i, j]?” | 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 | - |

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

Example: Burst Balloons (LC 312)

Think of it as: “which balloon do I burst last in the range [i, j]?” | 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 | - |

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

Example: Burst Balloons (LC 312)

Think of it as: “which balloon do I burst last in the range [i, j]?” | 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 | - |

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

Example: Burst Balloons (LC 312)

Think of it as: “which balloon do I burst last in the range [i, j]?” | 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 | - |

static int intervalDP(int[] arr) {
    int n = arr.length;
    int[][] dp = new int[n][n];

    // Base case: length 1
    for (int i = 0; i < n; i++) {
        dp[i][i] = arr[i]; // or base value
    }

    // Length 2 to n
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;

            // Try all splits
            for (int k = i; k < j; k++) {
                dp[i][j] = Math.max(dp[i][j],
                              dp[i][k] + dp[k+1][j] + cost(i, k, j));
            }
        }
    }

    return dp[0][n-1];
}

Example: Burst Balloons

static int maxCoins(int[] nums) {
    int n = nums.length;
    int[]arr = {1}
    arr.add(arr.iterator(), nums /* elements of nums */);
    arr.add(1);

    int[][] dp(n + 2, 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] = Math.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)

Template: With Cooldown (3 states)

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 - 
static int maxProfit(int[] prices) {
    int n = prices.length;
    // dp[i][0] = holding stock, dp[i][1] = not holding stock
    int[][] dp = new int[n][2];

    dp[0][0] = -prices[0]; // Buy on day 0
    dp[0][1] = 0;           // Don't buy on day 0

    for (int i = 1; i < n; i++) {
        // Hold: Math.max(keep holding, buy today)
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);
        // Not hold: Math.max(keep not holding, sell today)
        dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]);
    }

    return dp[n-1][1];
}

Template: Multiple States

static int maxProfit(int[] prices) {
    int n = prices.length;
    // States: rest, hold, sold (cooldown)
    int[][] dp = new int[n][3];

    dp[0][0] = 0;           // rest
    dp[0][1] = -prices[0];  // hold
    dp[0][2] = Integer.MIN_VALUE;     // sold

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

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

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.

ID Title Link Solution
337 House Robber III Link -
124 Binary Tree Maximum Path Sum Link -
968 Binary Tree Cameras Link - 
int[] dfs(TreeNode root) {
    if (!root) return new int[] {0, 0}
    var left = dfs(root.left);
    var right = dfs(root.right);

    // dp[0] = not take current, dp[1] = take current
    int notTake = Math.max(left[0], left[1]) +
                  Math.max(right[0], right[1]);
    int take = root.val + left[0] + right[0];

    return new int[] {notTake, take}
}

static int rob(TreeNode root) {
    var result = dfs(root);
    return Math.max(result[0], result[1]);
}

Template: Path Problems

static int maxPathSum(TreeNode root) {
    int maxSum = Integer.MIN_VALUE;

    function<int(TreeNode)> dfs = [&](TreeNode node) {
        if (!node) return 0;

        int left = Math.max(0, dfs(node.left));
        int right = Math.max(0, dfs(node.right));

        // Path through current node
        maxSum = Math.max(maxSum, node.val + left + right);

        // Return max path ending at current node
        return node.val + Math.max(left, right);
    }
    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.

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 - 
static int lengthOfLIS(int[] nums) {
    List<Integer> tails = new ArrayList<>();

    for (int num : nums) {
        var it = floorKey(tails /* elements of tails */, num);
        if (it == tails.iterator()) {
            tails.add(num);
        } else {
            *it = num;
        }
    }

    return tails.size();
}

Template: DP + Binary Search on Answer

// import java.util.Arrays;
// import java.util.Collections;
static int splitArray(int[] nums, int m) {
    int left = Arrays.stream(nums).Math.max().getAsInt();
    int right = accumulate(nums /* elements of nums */, 0);

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (canSplit(nums, m, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

static boolean canSplit(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;
}
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

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 - 
long dp[20][11][2][2]; String sN;
static long dfsDP(int i,int prev,boolean tight,boolean started){ if(i==(int)sN.size()) return started?1:0; var res =dp[i][prev+1][tight][started]; if(res!=-1) return res; res=0; int lim=tight?(sN[i]-'0'):9;
    for(int d=0; d<=lim; ++d){ boolean nt=tight && d==lim; boolean ns=started||d!=0; if(!ns || prev==-1 || d!=prev) res+=dfsDP(i+1, ns?d:prev, nt, ns); }
    return res; }
static long solveDP(long N){ sN=String.valueOf(N); memset(dp,-1,sizeof dp); return dfsDP = new return(0,-1,1,0); }
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)

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 - 
static int tsp(int[][] w){
    int n=w.size(); int INF=1e9; int[][] dp(1<<n, int[](n, INF));
    dp[1][0]=0; for(int mask=1; mask<(1<<n); ++mask){ for(int u=0; u<n; ++u) if(dp[mask][u]<INF){ for(int v=0; v<n; ++v) if(!(mask&(1<<v))) dp[mask|1<<v][v] = Math.min(dp[mask|1<<v][v], dp[mask][u]+w[u][v]); } }
    return min_element(dp.get(dp.length - 1).begin(), dp.get(dp.length - 1).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 -

More templates