Dynamic Programming Patterns

Problem: Houses in a row hold nums[i] money. You can't rob two adjacent houses. Maximize the loot.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ nums.length ≤ 100 · 0 ≤ nums[i] ≤ 400

From brute force to the pattern: Trying every set of non-adjacent houses is O(2ⁿ), and plain recursion recomputes the same sub-problems. Each prefix has one best answer, so DP fills them in order: O(n) time, O(1) space.

Spot it: "maximum" + "cannot take two adjacent" + an array. Each house is a take/skip choice, and the choices interact.

State & transition: dp[i] = best loot from houses 0..i. Last decision: rob house i (then house i−1 is off-limits → dp[i−2] + nums[i]) or skip it (dp[i−1]). The 1-D visualizer above fills this table.

Approach (step by step):

1. State: dp[i] = the most money from houses 0..i.
2. Transition: dp[i] = max(dp[i−1], dp[i−2] + nums[i]), i.e. skip house i or rob it.
3. Base: before any house the loot is 0, so both "previous" values start at 0.
4. Space: only the last two values are ever read, so keep two variables prev2 and prev1.
5. Answer: prev1 after the last house.

from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        # prev2 = dp[i - 2] and prev1 = dp[i - 1]; before any house the loot is 0
        prev2 = 0
        prev1 = 0
        for i in range(len(nums)):
            money = nums[i]
            # last decision for house i: skip it (keep prev1) or rob it (prev2 + money)
            best_here = max(prev1, prev2 + money)
            # slide the two-value window one house to the right
            prev2 = prev1
            prev1 = best_here
        return prev1

What the code is doing, line by line:

1. prev2 and prev1 are the last two cells of the dp table (dp[i - 2] and dp[i - 1]). Both start at 0 because before any house you have robbed nothing.
2. The loop visits every house by index and reads its money into money.
3. best_here is dp[i]: the better of skipping house i (the best so far stays prev1) or robbing it (then house i - 1 is off-limits, so add money to prev2).
4. Shift the window: the old prev1 becomes prev2, and best_here becomes prev1. The order matters: prev2 = prev1 must happen before prev1 is overwritten.
5. After the last house, prev1 is the best loot for the whole street.

Dry run on the example:

nums = [2, 7, 9, 3, 1] (answer 12 = 2 + 9 + 1):

i	money	skip = prev1	rob = prev2 + money	choice	new prev2	new prev1
0	2	0	2	rob	0	2
1	7	2	7	rob	2	7
2	9	7	11	rob	7	11
3	3	11	10	skip	11	11
4	1	11	12	rob	11	12

Edge cases to test:

• A single house.
• Two houses → the richer one.
• Skipping two houses in a row can be best, e.g. [2, 1, 1, 2] → 4.

Complexity: O(n) time, O(1) space (the 2-variable version of the table).

Problem: Can the array be split into two subsets with equal sums?

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 200 · 1 ≤ nums[i] ≤ 100

From brute force to the pattern: Trying all 2ⁿ subsets is exponential. The set of reachable sums is at most total / 2 + 1 values, so DP over sums is O(n · total).

Spot it: "can you partition" means picking a subset that sums to total/2. Each number is used at most once, so it's a yes/no 0/1 knapsack.

State & transition: dp[s] = "some subset of the items seen so far sums to s". For a new item x: dp[s] = dp[s] or dp[s − x]. Loop s downwards so dp[s − x] still means "without x". Looping upwards would let x be used twice.

Approach (step by step):

1. If the total is odd, return False right away.
2. target = total // 2. State: dp[s] = can some subset of the items seen so far sum to s?
3. Base: dp[0] = True (the empty subset).
4. For each number x, loop s from target down to x: dp[s] = dp[s] or dp[s − x].
5. Return dp[target].

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 == 1:
            return False                       # an odd total can't split into two equal halves
        target = total // 2
        # dp[subset_sum] = True if some subset of the numbers seen so far adds up to subset_sum
        # [False] * k makes a list of k False values
        dp = [False] * (target + 1)
        dp[0] = True                           # the empty subset sums to 0
        for i in range(len(nums)):
            num = nums[i]
            # walk subset_sum DOWN from target to num (BACKWARDS): dp[subset_sum - num]
            # is still the value from BEFORE this number, so each number is used at most once
            subset_sum = target
            while subset_sum >= num:
                if dp[subset_sum - num]:
                    dp[subset_sum] = True      # reach subset_sum by adding num to a smaller subset
                subset_sum = subset_sum - 1
        return dp[target]

What the code is doing, line by line:

1. Add up the numbers. If the total is odd, two equal halves are impossible, so return False immediately.
2. target is half the total. The question becomes: can some subset add up to exactly target?
3. dp has one True/False cell per possible sum 0..target. Only dp[0] starts True (pick nothing).
4. For each number num, a while loop walks subset_sum from target down to num. If subset_sum - num was reachable, adding num makes subset_sum reachable.
5. Why downwards? Cells below subset_sum have not been updated for this num yet, so they describe subsets without it. Going upwards would let num be added twice (for [2, 2, 3, 5], target 6, it would wrongly reach 6 as 3 + 3).
6. Return dp[target].

Dry run on the example:

nums = [1, 5, 11, 5], total 22, target = 11 (T = True, F = False):

dp[subset_sum] for subset_sum =	0	1	2	3	4	5	6	7	8	9	10	11
start	T	F	F	F	F	F	F	F	F	F	F	F
after num = 1	T	T	F	F	F	F	F	F	F	F	F	F
after num = 5	T	T	F	F	F	T	T	F	F	F	F	F
after num = 11	T	T	F	F	F	T	T	F	F	F	F	T
after num = 5	T	T	F	F	F	T	T	F	F	F	T	T

Edge cases to test:

• An odd total → False.
• A single element → False.
• One element equal to half the total.

Complexity: O(n · target) time, O(target) space.

Problem: Fewest coins (unlimited supply of each denomination) that make up amount, or -1 if impossible.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ coins.length ≤ 12 · 1 ≤ coins[i] ≤ 2³¹ - 1 · 0 ≤ amount ≤ 10⁴

From brute force to the pattern: Greedy (biggest coin first) can fail, e.g. coins [1, 3, 4] for 6; plain recursion is exponential. Unbounded-knapsack DP over amounts is O(amount · coins).

Spot it: "fewest" + "infinite number of each coin". That's unbounded knapsack. Greedy fails: with coins [1,3,4] and amount 6, greedy gives 4+1+1, but 3+3 is better.

State & transition: dp[a] = fewest coins to make amount a. Last decision: which coin c was added last → dp[a] = 1 + min(dp[a − c]). Fill a upwards.

Approach (step by step):

1. State: dp[a] = fewest coins that make amount a.
2. Base: dp[0] = 0. Every other cell starts at a sentinel INF = amount + 1 (impossible).
3. For a = 1..amount (forwards), for each coin c ≤ a: dp[a] = min(dp[a], dp[a − c] + 1). Coin c is the last coin added.
4. If dp[amount] is still INF, return -1. Otherwise return it.

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        INF = amount + 1                        # "impossible": more coins than could ever be needed
        # dp[sub_amount] = fewest coins that make sub_amount; every cell starts as impossible
        dp = [INF] * (amount + 1)
        dp[0] = 0                               # 0 coins make amount 0
        # fill amounts FORWARDS so smaller amounts are ready (and coins can be reused)
        for sub_amount in range(1, amount + 1):
            for i in range(len(coins)):
                coin = coins[i]
                if coin <= sub_amount:
                    # use this coin LAST: 1 coin + best way to make the rest
                    dp[sub_amount] = min(dp[sub_amount], dp[sub_amount - coin] + 1)
        if dp[amount] == INF:
            return -1                           # never reached: amount can't be made
        return dp[amount]

What the code is doing, line by line:

1. INF = amount + 1 is a sentinel for "impossible": even using only 1-coins you never need more than amount coins.
2. dp starts with every amount impossible, except dp[0] = 0.
3. The outer loop walks sub_amount from 1 up to amount. For each coin that fits, it asks: "if this coin is the last one I add, how many coins in total?" That is dp[sub_amount - coin] + 1, and we keep the minimum.
4. Because smaller amounts are finished first, dp[sub_amount - coin] is always final when we read it, and it may itself already use the same coin (unlimited supply).
5. If dp[amount] is still INF, no combination works and we return -1; otherwise we return the count.

Dry run on the example:

coins = [1, 2, 5], amount = 11 (answer 3 = 5 + 5 + 1). "Best last coin" is the first coin that achieved the minimum:

sub_amount	dp[sub_amount]	best last coin
0	0	—
1	1	coin 1 + dp[0] (= 0)
2	1	coin 2 + dp[0] (= 0)
3	2	coin 1 + dp[2] (= 1)
4	2	coin 2 + dp[2] (= 1)
5	1	coin 5 + dp[0] (= 0)
6	2	coin 1 + dp[5] (= 1)
7	2	coin 2 + dp[5] (= 1)
8	3	coin 1 + dp[7] (= 2)
9	3	coin 2 + dp[7] (= 2)
10	2	coin 5 + dp[5] (= 1)
11	3	coin 1 + dp[10] (= 2)

Edge cases to test:

• amount = 0 → 0.
• Impossible amounts → −1.
• A single coin type.

Complexity: O(amount · len(coins)) time, O(amount) space.

Problem: Minimum number of single-character inserts, deletes, or replaces to turn word1 into word2.

Solve it on LeetCode ↗

Constraints: 0 ≤ word1.length, word2.length ≤ 500 · word1 and word2 consist of lowercase English letters.

From brute force to the pattern: Recursing on the three operations without memory is exponential. There are only (m + 1)(n + 1) prefix pairs, so a DP table fills them all in O(m · n).

Spot it: two strings + "minimum operations". That's the 2-D string family, a sibling of LCS (shown in the table-fill visualizer above).

State & transition: dp[i][j] = edits to turn word1[:i] into word2[:j]. If the last characters match: dp[i−1][j−1] (free). Otherwise 1 + min(delete → dp[i−1][j], insert → dp[i][j−1], replace → dp[i−1][j−1]). Base: dp[i][0] = i, dp[0][j] = j.

Approach (step by step):

1. State: dp[i][j] = edits to turn word1[:i] into word2[:j]. The table is (m+1) × (n+1).
2. Base: dp[i][0] = i (delete everything) and dp[0][j] = j (insert everything).
3. Fill row by row. If word1[i−1] == word2[j−1], copy the diagonal (no edit needed).
4. Otherwise take 1 + min(up = delete, left = insert, diagonal = replace).
5. Answer: dp[m][n].

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        len1 = len(word1)                       # m in the steps above
        len2 = len(word2)                       # n in the steps above
        # build a (len1 + 1) x (len2 + 1) table of zeros, one row at a time
        dp = []
        for i in range(len1 + 1):
            dp.append([0] * (len2 + 1))
        # base cases: turning a prefix into "" (or "" into a prefix) costs its length
        for i in range(len1 + 1):
            dp[i][0] = i                        # delete everything
        for j in range(len2 + 1):
            dp[0][j] = j                        # insert everything
        for i in range(1, len1 + 1):
            for j in range(1, len2 + 1):
                if word1[i - 1] == word2[j - 1]:
                    # last characters already match: no edit needed
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    delete_cost = dp[i - 1][j]        # delete word1[i - 1]
                    insert_cost = dp[i][j - 1]        # insert word2[j - 1]
                    replace_cost = dp[i - 1][j - 1]   # replace word1[i - 1] with word2[j - 1]
                    dp[i][j] = 1 + min(delete_cost, insert_cost, replace_cost)
        return dp[len1][len2]

What the code is doing, line by line:

1. len1 and len2 are the word lengths (called m and n in the steps above).
2. The table is built with a loop that appends one row of zeros per prefix of word1 (including the empty prefix), giving (len1 + 1) × (len2 + 1) cells.
3. Column 0 and row 0 are the base cases: turning word1[:i] into an empty string takes i deletes; turning an empty string into word2[:j] takes j inserts.
4. For every other cell we compare the last characters of the two prefixes. If they match, the cost is the same as without them (the diagonal cell).
5. Otherwise we pay 1 edit plus the cheapest of three neighbors: up (delete_cost), left (insert_cost) or diagonal (replace_cost).
6. The bottom-right cell dp[len1][len2] is the answer for the full words.

Dry run on the example:

word1 = "horse", word2 = "ros". Each cell is dp[i][j]; the answer is the bottom-right 3:

word1 ↓ / word2 →	""	r	o	s
""	0	1	2	3
h	1	1	2	3
o	2	2	1	2
r	3	2	2	2
s	4	3	3	2
e	5	4	4	3

Edge cases to test:

• One word empty → the other word's length.
• Identical words → 0.
• No letters in common.

Complexity: O(m·n) time; O(m·n) space, or O(n) keeping two rows.

Problem: Length of the longest strictly increasing subsequence (elements don't have to be contiguous).

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ nums.length ≤ 2500 · -10⁴ ≤ nums[i] ≤ 10⁴

From brute force to the pattern: Checking all 2ⁿ subsequences is exponential. The O(n²) DP reuses the answer for every earlier ending; patience sorting with binary search brings it to O(n log n).

Spot it: "longest" + "subsequence" + one array.

State & transition: dp[i] = length of the longest increasing subsequence that ends at index i. Last decision: which earlier j (with nums[j] < nums[i]) comes right before i. The answer is max(dp), because the best subsequence can end anywhere.

Approach (step by step):

1. State: dp[i] = length of the longest increasing subsequence that ends at index i. Start every cell at 1.
2. For each i, look at every j < i. If nums[j] < nums[i], nums[i] can extend that subsequence: dp[i] = max(dp[i], dp[j] + 1).
3. Answer: max(dp), because the best subsequence can end anywhere.
4. Faster version: keep tails, where tails[k] = the smallest possible tail of an increasing subsequence of length k+1. Binary-search each x into it: append if it's larger than every tail, otherwise overwrite the first tail ≥ x. The answer is len(tails).

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:          # O(n^2) DP
        # dp[i] = length of the longest increasing subsequence that ENDS at index i
        # every element alone is a run of length 1, so start every cell at 1
        dp = [1] * len(nums)
        for i in range(len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    # nums[i] can extend the run that ends at j
                    dp[i] = max(dp[i], dp[j] + 1)
        # the best run may end anywhere, so take the largest cell (0 for an empty list)
        best = 0
        for i in range(len(dp)):
            best = max(best, dp[i])
        return best

    def lengthOfLIS_fast(self, nums: List[int]) -> int:     # O(n log n)
        # tails[k] = smallest possible last number of an increasing subsequence of length k + 1
        # (tails is always sorted, which is what makes binary search possible)
        tails = []
        for i in range(len(nums)):
            num = nums[i]
            position = self.first_tail_at_least(tails, num)
            if position == len(tails):
                tails.append(num)               # num is bigger than every tail: the longest run grows
            else:
                tails[position] = num           # num is a smaller tail for runs of length position + 1
        return len(tails)

    def first_tail_at_least(self, tails: List[int], num: int) -> int:
        # binary search: return the first index whose value is >= num,
        # or len(tails) if every value is smaller than num
        low = 0
        high = len(tails)                       # the answer is always inside [low, high]
        while low < high:
            middle = (low + high) // 2
            if tails[middle] < num:
                low = middle + 1                # middle is too small, the answer is to its right
            else:
                high = middle                   # middle might be the answer, keep it in range
        return low                              # low == high: the window has shrunk to one spot

What the code is doing, line by line:

1. Slow version. dp starts as all 1s: every number on its own is an increasing run of length 1.
2. For each i, the inner loop looks at every earlier index j. If nums[j] < nums[i], then nums[i] can be appended to the best run ending at j, giving length dp[j] + 1.
3. The longest run can end at any index, so a final loop finds the largest value in dp. Starting best at 0 also handles an empty list.
4. Fast version. tails[k] remembers the smallest number that can end an increasing run of length k + 1. A smaller tail is always better, because more future numbers can extend it. tails stays sorted.
5. For each num, the helper finds position = the first tail that is >= num. If there is none, num extends the longest run, so it is appended. Otherwise num replaces that tail: we found a run of the same length with a smaller ending.
6. The hand-written binary search (first_tail_at_least): the answer is somewhere in low..high (where high = len(tails) means "after the end"). Look at the middle element. If it is smaller than num, the answer must be to the right, so low = middle + 1. Otherwise middle itself might be the answer, so high = middle. Each step halves the window; when low == high the loop stops and low is the answer. (Python's bisect.bisect_left does the same thing.)
7. The length of tails is the LIS length. Careful: tails itself is not always a real subsequence; only its length is meaningful.

Dry run on the example:

nums = [10, 9, 2, 5, 3, 7, 101, 18] (answer 4, e.g. 2, 3, 7, 18). Both versions side by side:

i	nums[i]	dp[i] (slow version)	position (binary search)	action	tails after
0	10	1	0	append	[10]
1	9	1	0	overwrite tails[0]	[9]
2	2	1	0	overwrite tails[0]	[2]
3	5	2	1	append	[2, 5]
4	3	2	1	overwrite tails[1]	[2, 3]
5	7	3	2	append	[2, 3, 7]
6	101	4	3	append	[2, 3, 7, 101]
7	18	4	3	overwrite tails[3]	[2, 3, 7, 18]

Edge cases to test:

• Strictly decreasing → 1.
• Equal values don't count as increasing.
• A single element.

Complexity: O(n²) / O(n log n) time, O(n) space.

Problem: Bursting balloon i earns nums[left] · nums[i] · nums[right], using its current neighbors. Missing neighbors count as 1. Maximize total coins.

Solve it on LeetCode ↗

Constraints: n == nums.length · 1 ≤ n ≤ 300 · 0 ≤ nums[i] ≤ 100

From brute force to the pattern: Trying every burst order is O(n!). Fixing the last balloon splits the range into two independent halves, giving an interval DP in O(n³).

Spot it: the order of removals changes the neighbors, and the answer for a range depends on sub-ranges. That's interval DP.

Key insight (the trick): don't think about which balloon bursts first. That splits the problem into halves that still interact. Think about which balloon k bursts last inside the open interval (l, r). When it bursts, its neighbors are exactly l and r, and the two sides are independent: dp[l][r] = max(dp[l][k] + a[l]·a[k]·a[r] + dp[k][r]).

Approach (step by step):

1. Pad the array with a 1 at each end. This encodes the "missing neighbor counts as 1" rule.
2. State: dp[l][r] = the most coins from bursting every balloon strictly between l and r.
3. Fill by increasing interval length, so shorter intervals are always ready first.
4. Transition: try each k in (l, r) as the last balloon burst: dp[l][k] + a[l]·a[k]·a[r] + dp[k][r].
5. Answer: dp[0][n−1].

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        # pad with a 1 on each side: the "missing neighbor counts as 1" rule
        # (list + list glues two lists together)
        balloons = [1] + nums + [1]
        size = len(balloons)
        # build a size x size table of zeros, one row at a time
        # dp[left][right] = most coins from bursting every balloon strictly between left and right
        dp = []
        for i in range(size):
            dp.append([0] * size)
        # short intervals before long ones, so the pieces are always ready
        for length in range(2, size):
            for left in range(size - length):
                right = left + length
                # try every balloon in (left, right) as the LAST one to burst there;
                # at that moment its neighbors are exactly balloons[left] and balloons[right]
                for last in range(left + 1, right):
                    burst_last = balloons[left] * balloons[last] * balloons[right]
                    total = dp[left][last] + burst_last + dp[last][right]
                    dp[left][right] = max(dp[left][right], total)
        return dp[0][size - 1]

What the code is doing, line by line:

1. balloons is nums with an extra 1 at both ends, so every real balloon always has two neighbors.
2. The table dp is built row by row with append. dp[left][right] means: the best total from bursting only the balloons strictly between positions left and right. Intervals with nothing inside (right = left + 1) stay 0.
3. length is the distance right - left, going from 2 (one balloon inside) up to the whole array. Shorter intervals are filled first.
4. For each interval, every last in between is tried as the final balloon burst there. Everything else inside was already burst, so its neighbors are balloons[left] and balloons[right]; it earns burst_last.
5. The left part (left, last) and the right part (last, right) are independent, and their best totals are already in the table. total adds the three pieces; we keep the maximum.
6. The answer is the interval covering all real balloons: dp[0][size - 1].

Dry run on the example:

nums = [3, 1, 5, 8] → balloons = [1, 3, 1, 5, 8, 1]. Headers show index (value); each cell is dp[left][right], · = empty or impossible interval. Answer: top-right 167.

left ↓ / right →	0 (1)	1 (3)	2 (1)	3 (5)	4 (8)	5 (1)
0 (1)	·	·	3	30	159	167
1 (3)	·	·	·	15	135	159
2 (1)	·	·	·	·	40	48
3 (5)	·	·	·	·	·	40
4 (8)	·	·	·	·	·	·
5 (1)	·	·	·	·	·	·

Edge cases to test:

• A single balloon.
• Zeros in the array.
• Pad the array with 1 at both ends.

Complexity: O(n³) time, O(n²) space. [3,1,5,8] → 167.

Problem: Move only right or down from the top-left to the bottom-right, minimizing the sum of the cells you pass through.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: m == grid.length · n == grid[i].length · 1 ≤ m, n ≤ 200 · 0 ≤ grid[i][j] ≤ 200

From brute force to the pattern: Trying every right/down path is exponential. Each cell's best cost depends only on its two predecessors, so a grid DP is O(r · c).

Spot it: grid + "only right or down" + "minimum". With one-way moves there are no cycles, so it's grid DP rather than BFS/Dijkstra.

State & transition: dp[r][c] = grid[r][c] + min(dp[r−1][c], dp[r][c−1]). Only the previous row is needed, so one 1-D array suffices.

Approach (step by step):

1. State: dp[r][c] = cheapest path sum to reach (r, c). Keep only one row: dp of size num_cols + 1.
2. dp[0] stays ∞ as a left-wall sentinel. Set dp[1] = 0 so the start cell costs just its own value.
3. For each row, go left to right: dp[j+1] = cell + min(dp[j+1] (from above), dp[j] (from the left)).
4. Answer: dp[num_cols] after the last row.

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        num_cols = len(grid[0])
        # dp[j + 1] = cheapest path sum to reach column j of the current row.
        # dp[0] is an extra "wall" cell that is never reachable.
        # float("inf") is bigger than any number, so it means "can't come from here"
        dp = [float("inf")] * (num_cols + 1)
        dp[1] = 0                                # so the start cell costs just grid[0][0]
        for i in range(len(grid)):
            row = grid[i]
            for j in range(num_cols):
                from_above = dp[j + 1]           # still holds the PREVIOUS row's value
                from_left = dp[j]                # already updated for THIS row
                dp[j + 1] = row[j] + min(from_above, from_left)
        return dp[num_cols]

What the code is doing, line by line:

1. Instead of a full 2-D table we keep one row, dp, with one extra cell at the front. dp[j + 1] is the cheapest way to reach column j; dp[0] is a wall that is always infinity.
2. Before the first row everything is unreachable except dp[1] = 0. That makes the start cell cost exactly grid[0][0] (coming "from above" for free).
3. For each row (left to right), dp[j + 1] still holds the value from the row above (from_above), and dp[j] was just updated for this row (from_left). The new value is the cell's own cost plus the cheaper of the two.
4. In row 0, from_above is infinity (except at the start), so cells can only be reached from the left. In column 0, from_left is the wall, so cells can only be reached from above.
5. After the last row, dp[num_cols] is the cheapest path to the bottom-right corner.

Dry run on the example:

grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]] (answer 7 = 1→3→1→1→1). The single dp row after each grid row:

	row values	dp[0] (wall)	dp[1] (col 0)	dp[2] (col 1)	dp[3] (col 2)
start	—	∞	0	∞	∞
after row 0	[1, 3, 1]	∞	1	4	5
after row 1	[1, 5, 1]	∞	2	7	6
after row 2	[4, 2, 1]	∞	6	8	7

Edge cases to test:

• A single row or column.
• A 1 × 1 grid.
• Large values along the edges.

Complexity: O(R·C) time, O(C) space.

Problem: Unlimited transactions, but after selling you must wait one day before buying again. Maximize profit.

Solve it on LeetCode ↗

Constraints: 1 ≤ prices.length ≤ 5000 · 0 ≤ prices[i] ≤ 1000

From brute force to the pattern: Trying every sequence of buy/sell/rest is exponential. Three states per day with constant-time transitions is O(n) time and O(1) space.

Spot it: "after you sell, you cannot buy the next day". What you're allowed to do depends on what you are right now. Model it as a few states with arrows between them.

States: hold (own a share), sold (just sold today, so cooling down tomorrow), rest (no share, free to buy). Arrows: hold ← max(hold, rest − p), sold ← hold + p, rest ← max(rest, sold).

Approach (step by step):

1. Define three states for the end of each day: hold (own a share), sold (sold today), rest (no share and free to buy).
2. Start with hold = sold = −∞ (impossible before day 0) and rest = 0.
3. Each day, compute all three from yesterday's values: hold = max(hold, rest − p), sold = hold + p, rest = max(rest, sold).
4. Buying reads rest, never sold. That one detail enforces the cooldown.
5. Answer: max(sold, rest). Ending while holding a share is never best.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # float("-inf") = "impossible": before day 0 you can't own a share or have just sold one
        hold = float("-inf")                     # own a share
        sold = float("-inf")                     # sold today (cooling down tomorrow)
        rest = 0                                 # no share and free to buy
        for i in range(len(prices)):
            price = prices[i]
            # all three must be computed from YESTERDAY's values, so we store the
            # new values in temporary variables and only copy them over at the end
            new_hold = max(hold, rest - price)   # keep holding, or buy today (only from rest)
            new_sold = hold + price              # sell the share we held yesterday
            new_rest = max(rest, sold)           # keep resting, or finish yesterday's cooldown
            hold = new_hold
            sold = new_sold
            rest = new_rest
        return max(sold, rest)                   # ending while holding a share is never best

What the code is doing, line by line:

1. Three variables, one per state, each holding the best profit you can have at the end of the current day in that state.
2. hold and sold start at minus infinity because neither state is possible before the first day; rest starts at 0.
3. Each day computes new_hold, new_sold and new_rest from yesterday's values. The temporaries are needed because, for example, new_sold uses yesterday's hold; if we had already overwritten hold, we could buy and sell on the same day, and new_rest would see today's sold and skip the cooldown.
4. Buying reads rest, never sold: that is the cooldown. After a sale you spend a day in sold before moving to rest, and only then can you buy.
5. The answer is the better of sold and rest.

Dry run on the example:

prices = [1, 2, 3, 0, 2] (answer 3: buy, sell, cooldown, buy, sell). Values at the end of each day:

day	price	hold	sold	rest
start	—	−∞	−∞	0
0	1	-1	−∞	0
1	2	-1	1	0
2	3	-1	2	1
3	0	1	-1	2
4	2	1	3	2

Edge cases to test:

• A single day → 0.
• Falling prices → 0.
• The cooldown forcing you to skip a good buy.

Complexity: O(n) time, O(1) space.

Problem: You climb a staircase of n steps, 1 or 2 steps at a time. In how many distinct ways can you reach the top?

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ n ≤ 45

From brute force to the pattern: Plain recursion recomputes the same steps exponentially often (O(2ⁿ)). Building up from the bottom computes each value once: O(n) time, O(1) space.

Spot it: "how many distinct ways" + each move is a small choice is 1-D DP, and it's Fibonacci in disguise.

Approach (step by step):

1. State: ways(i) = number of ways to stand on step i.
2. Last decision: the final move was either 1 step (from i−1) or 2 steps (from i−2), so ways(i) = ways(i−1) + ways(i−2).
3. Base: ways(0) = 1 (stand still) and ways(1) = 1.
4. Only two previous values are needed, so roll two variables up to n.

class Solution:
    def climbStairs(self, n: int) -> int:
        prev2 = 1                                 # ways(0): standing still is 1 way
        prev1 = 1                                 # ways(1): a single 1-step
        for step in range(2, n + 1):
            # the last move onto this step was a 1-step (from step - 1) or a 2-step (from step - 2)
            ways_here = prev1 + prev2
            # slide the window up one step
            prev2 = prev1
            prev1 = ways_here
        return prev1

What the code is doing, line by line:

1. prev2 and prev1 hold the number of ways to reach the two steps just below the current one. Both start at 1 (ways(0) and ways(1)).
2. For every step from 2 to n, the ways to stand on it are the ways to reach the step below (then take 1 step) plus the ways to reach two below (then take 2 steps).
3. Then the window slides: prev2 takes the old prev1, and prev1 takes ways_here.
4. If n is 1 the loop never runs and prev1 = 1 is returned. Otherwise prev1 ends as ways(n).

Dry run on the example:

n = 5 (answer 8). The LeetCode examples n = 2 → 2 and n = 3 → 3 appear in the first two loop rows:

step	ways_here = prev1 + prev2	new prev2	new prev1
start	—	1	1
2	2	1	2
3	3	2	3
4	5	3	5
5	8	5	8

Edge cases to test:

• n = 1 → 1.
• n = 2 → 2.
• Large n (the recursion would be far too slow).

Complexity: O(n) time, O(1) space.

Problem: House Robber (198), but the houses stand in a circle: the first and last houses are neighbors.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 100 · 0 ≤ nums[i] ≤ 1000

From brute force to the pattern: Handling the circle with complex state is error-prone. Splitting into two straight-line problems reuses House Robber: O(n).

Spot it: This is the same 1-D take/skip DP. The circle only adds one conflict: you can't rob both house 0 and house n−1.

Approach (step by step):

1. If there is only one house, return its value.
2. Case A: ignore the last house and run the linear robber on nums[:-1].
3. Case B: ignore the first house and run it on nums[1:].
4. Every valid plan skips the first house or the last one (or both), so the answer is max(A, B).

from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]                         # nums[1:] and nums[:-1] would both be empty
        # break the circle two ways (slices make new lists):
        without_last = self.rob_line(nums[:-1])    # everything except the last house
        without_first = self.rob_line(nums[1:])    # everything except the first house
        return max(without_last, without_first)

    def rob_line(self, houses: List[int]) -> int:
        # House Robber I (houses in a straight line) in O(1) space
        prev2 = 0                                  # best loot up to two houses back
        prev1 = 0                                  # best loot up to the previous house
        for i in range(len(houses)):
            money = houses[i]
            best_here = max(prev1, prev2 + money)  # skip this house, or rob it
            prev2 = prev1
            prev1 = best_here
        return prev1

What the code is doing, line by line:

1. With a single house there is no conflict, so return its value. (Both slices below would be empty and give 0.)
2. In a circle the first and last houses are neighbors, so no plan robs both. Every valid plan therefore fits inside nums[:-1] (all but the last house) or inside nums[1:] (all but the first).
3. Each of those is an ordinary straight street, solved by the helper method rob_line, which is exactly the House Robber I solution from problem 198.
4. rob_line keeps prev2 and prev1, picks the better of skipping or robbing each house, and slides the window.
5. The answer is the larger of the two straight-line results.

Dry run on the example:

nums = [1, 2, 3, 1]: case A uses [1, 2, 3], case B uses [2, 3, 1]. Answer max(4, 3) = 4.

case	money	new prev2	new prev1
A: nums[:-1]	1	0	1
A: nums[:-1]	2	1	2
A: nums[:-1]	3	2	4
B: nums[1:]	2	0	2
B: nums[1:]	3	2	3
B: nums[1:]	1	3	3

Edge cases to test:

• A single house (the two ranges would be empty).
• Two houses.
• The best answer uses the first house.

Complexity: O(n) time, O(n) for the slices (or O(1) with index ranges).

Problem: Count the number of combinations of coins (unlimited supply) that make up amount. Order doesn't matter, so 1+2 and 2+1 are the same combination.

Solve it on LeetCode ↗

Constraints: 1 ≤ coins.length ≤ 300 · 1 ≤ coins[i] ≤ 5000 · All the values of coins are unique. · 0 ≤ amount ≤ 5000

From brute force to the pattern: Recursion over coin choices is exponential, and swapping the two loops counts orderings by mistake. The coins-outer DP counts each combination once in O(amount · coins).

Spot it: "number of combinations" + unlimited coins is unbounded knapsack, counting version. Loop order decides whether you count combinations or permutations.

Approach (step by step):

1. State: dp[a] = number of ways to make a using the coins processed so far.
2. Base: dp[0] = 1 (one way to make 0: take nothing).
3. Coins in the outer loop, amounts in the inner loop going forwards: dp[a] += dp[a − c].
4. Coins outside means each combination is built in a fixed coin order, so it's counted once. Forwards means each coin may be reused.

from typing import List

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # dp[sub_amount] = number of ways to make sub_amount with the coins processed so far
        dp = [0] * (amount + 1)                     # [0] * k = k zeros
        dp[0] = 1                                   # one way to make 0: take no coins
        # coins in the OUTER loop -> each combination is built in a fixed coin order,
        # so 1+2 and 2+1 are counted only once
        for i in range(len(coins)):
            coin = coins[i]
            # amounts FORWARDS -> dp[sub_amount - coin] may already use this coin, so it can be reused
            for sub_amount in range(coin, amount + 1):
                # add the ways that end with (another) copy of this coin
                dp[sub_amount] = dp[sub_amount] + dp[sub_amount - coin]
        return dp[amount]

What the code is doing, line by line:

1. dp counts ways per amount. dp[0] = 1: there is exactly one way to make 0 (use nothing), and that is what lets the first coin get counted.
2. The outer loop goes over coins. After finishing coin number i, dp counts combinations that use only the first i + 1 coins. Because coins are added in a fixed order, each combination is counted once.
3. The inner loop goes forwards over amounts from coin to amount. dp[sub_amount - coin] may already include this coin, so taking it again is allowed (unlimited supply).
4. Each update adds the ways that make sub_amount - coin and then finish with this coin.
5. Swapping the two loops (amounts outside) would count orders, i.e. permutations, which is a different problem (LeetCode 377).

Dry run on the example:

amount = 5, coins = [1, 2, 5] (answer 4). The dp array after each coin:

dp[sub_amount] for sub_amount =	0	1	2	3	4	5
start	1	0	0	0	0	0
after coin = 1	1	1	1	1	1	1
after coin = 2	1	1	2	2	3	3
after coin = 5	1	1	2	2	3	4

Edge cases to test:

• amount = 0 → 1 (the empty combination).
• No way to make the amount → 0.
• A coin larger than the amount.

Complexity: O(amount · len(coins)) time, O(amount) space.

Problem: Return the length of the longest subsequence that appears in both strings (characters in order, not necessarily contiguous).

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ text1.length, text2.length ≤ 1000 · text1 and text2 consist of only lowercase English characters.

From brute force to the pattern: Comparing all subsequences of both strings is O(2^(m + n)). There are only m · n prefix pairs, so the DP table is O(m · n).

Spot it: Two strings + "longest common subsequence" is the base two-string DP. The table-filling visualizer in section 2 runs exactly this algorithm.

Approach (step by step):

1. State: dp[i][j] = LCS length of a[:i] and b[:j]. The table is (m+1) × (n+1), and row 0 / column 0 (empty prefixes) are 0.
2. If a[i−1] == b[j−1], both last characters join the LCS: dp[i][j] = dp[i−1][j−1] + 1.
3. Otherwise drop one of the two last characters: dp[i][j] = max(dp[i−1][j], dp[i][j−1]).
4. Fill row by row. The answer is dp[m][n].

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        len1 = len(text1)                         # m in the steps above
        len2 = len(text2)                         # n in the steps above
        # build a (len1 + 1) x (len2 + 1) table of zeros, one row at a time;
        # the extra row/column stands for the empty prefix
        dp = []
        for i in range(len1 + 1):
            dp.append([0] * (len2 + 1))
        for i in range(1, len1 + 1):
            for j in range(1, len2 + 1):
                # dp index i matches string index i - 1
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1               # both characters join the LCS
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])    # drop a character from one side
        return dp[len1][len2]

What the code is doing, line by line:

1. len1 and len2 are the lengths (m and n in the steps).
2. The table gets one row of zeros per prefix of text1, including the empty prefix. Row 0 and column 0 stay 0: nothing is common with an empty string.
3. Cell dp[i][j] describes text1[:i] and text2[:j], so their last characters are text1[i - 1] and text2[j - 1].
4. If they are equal, both join the common subsequence: take the diagonal and add 1.
5. If not, at least one of them is not in the LCS, so take the better of dropping the last character of text1 (cell above) or of text2 (cell to the left).
6. The answer is in the bottom-right cell.

Dry run on the example:

text1 = "abcde", text2 = "ace" (answer 3, "ace"). Each cell is dp[i][j]:

text1 ↓ / text2 →	""	a	c	e
""	0	0	0	0
a	0	1	1	1
b	0	1	1	1
c	0	1	2	2
d	0	1	2	2
e	0	1	2	3

Edge cases to test:

• No common letters → 0.
• Identical strings → their length.
• One string empty.

Complexity: O(m·n) time; O(m·n) space, or O(n) with two rows.

Problem: Implement matching with '.' (any single character) and '*' (zero or more of the preceding element). The pattern must match the entire string.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 20 · 1 ≤ p.length ≤ 20 · s contains only lowercase English letters. · p contains only lowercase English letters, '.', and '*'. · It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

From brute force to the pattern: Naive recursion on * branches exponentially. Memoising on (i, j) limits it to m · n states: O(m · n).

Spot it: Two strings, prefix vs prefix, yes/no is two-string DP. The '*' adds a "use it zero times / use it once more" choice.

Approach (step by step):

1. State: dp[i][j] = does s[:i] match p[:j]? Base: dp[0][0] = True.
2. Empty string vs pattern: dp[0][j] = dp[0][j−2] when p[j−1] == '*'. Patterns like a*b* can match nothing.
3. If p[j−1] is a letter or '.': dp[i][j] = dp[i−1][j−1] and the characters match.
4. If p[j−1] == '*': either use "x*" zero times (dp[i][j−2]), or, if s[i−1] matches x, eat one more character with it (dp[i−1][j]).
5. Answer: dp[m][n].

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        len_s = len(s)
        len_p = len(p)
        # build a (len_s + 1) x (len_p + 1) table of False, one row at a time
        # dp[i][j] = does s[:i] (first i characters) match p[:j] (first j pattern characters)?
        dp = []
        for i in range(len_s + 1):
            dp.append([False] * (len_p + 1))
        dp[0][0] = True                                   # empty matches empty
        # empty string vs pattern: only "x*" pairs can match nothing
        for j in range(2, len_p + 1):
            if p[j - 1] == "*":
                dp[0][j] = dp[0][j - 2]                   # "x*" can vanish
        for i in range(1, len_s + 1):
            for j in range(1, len_p + 1):
                if p[j - 1] == "*":
                    # option 1: use "x*" zero times -> skip both pattern characters
                    zero_times = dp[i][j - 2]
                    # option 2: "x*" eats s[i - 1] (if x matches it) and stays available
                    one_more = False
                    if dp[i - 1][j] and self.chars_match(s[i - 1], p[j - 2]):
                        one_more = True
                    dp[i][j] = zero_times or one_more
                else:
                    # plain letter or ".": the last characters must match, and so must the rest
                    dp[i][j] = dp[i - 1][j - 1] and self.chars_match(s[i - 1], p[j - 1])
        return dp[len_s][len_p]

    def chars_match(self, text_char: str, pattern_char: str) -> bool:
        # "." matches any single character; anything else must be equal
        if pattern_char == ".":
            return True
        return text_char == pattern_char

What the code is doing, line by line:

1. The table has one row per prefix of s and one column per prefix of p, all starting as False, built row by row with append. dp[0][0] = True because an empty pattern matches an empty string.
2. Row 0 (empty string): a pattern can only match nothing if it is made of x* pairs. When p[j - 1] is *, copy the answer from two columns back (drop the pair).
3. For a * at p[j - 1], the element it repeats is p[j - 2]. zero_times drops the pair entirely. one_more says: if s[i - 1] matches that element, let the star swallow it and look at dp[i - 1][j] (same pattern, string one character shorter), because the star can still be used again.
4. For a plain letter or ., the last characters must match and the shorter prefixes (dp[i - 1][j - 1]) must match too.
5. The helper method chars_match handles the . wildcard so the main loop stays readable.
6. dp[len_s][len_p] says whether the whole string matches the whole pattern.

Dry run on the example:

s = "aab", p = "c*a*b" (answer True: c* vanishes, a* eats "aa", b matches). T = True, F = False:

s ↓ / p →	""	c	*	a	*	b
""	T	F	T	F	T	F
a	F	F	F	T	T	F
a	F	F	F	F	T	F
b	F	F	F	F	F	T

Edge cases to test:

• .* matches anything, including an empty string.
• a* matching zero as.
• The pattern is longer than the string but still matches, e.g. s = "", p = "a*".

Complexity: O(m·n) time and space.

Problem: Make at most two transactions (buy then sell, never holding two shares at once). Maximize profit.

Solve it on LeetCode ↗

Constraints: 1 ≤ prices.length ≤ 10⁵ · 0 ≤ prices[i] ≤ 10⁵

From brute force to the pattern: Splitting the days at every point and solving two single-transaction problems is O(n²) (or O(n) with prefix/suffix arrays). Four rolling states do it in O(n) time and O(1) space.

Spot it: This is a state machine: what you may do depends on how many buys and sells you've already made. Four states in a chain: buy1 → sell1 → buy2 → sell2.

Approach (step by step):

1. buy1 = best balance after the first buy, sell1 = after the first sell, buy2 = after the second buy, sell2 = after the second sell.
2. Start with buy1 = buy2 = −∞ (not possible yet) and sell1 = sell2 = 0.
3. For each price p: buy1 = max(buy1, −p), sell1 = max(sell1, buy1 + p), buy2 = max(buy2, sell1 − p), sell2 = max(sell2, buy2 + p).
4. Updating in this order with same-day values is safe. Buying and selling on the same day gains 0, so it never creates fake profit.
5. Answer: sell2. It also covers doing only one transaction, or none.

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # float("-inf") = "impossible": you can't be holding a share before any price is seen
        buy1 = float("-inf")              # best balance after the first buy
        buy2 = float("-inf")              # best balance after the second buy
        sell1 = 0                         # best balance after the first sell (or doing nothing)
        sell2 = 0                         # best balance after the second sell
        for i in range(len(prices)):
            price = prices[i]
            buy1 = max(buy1, -price)          # first buy: pay price from a balance of 0
            sell1 = max(sell1, buy1 + price)  # first sell
            buy2 = max(buy2, sell1 - price)   # second buy reuses the profit of the first sale
            sell2 = max(sell2, buy2 + price)  # second sell
        return sell2

What the code is doing, line by line:

1. Four variables track the best money balance after each stage of the chain buy1 → sell1 → buy2 → sell2. The buys start at minus infinity (not possible yet); the sells start at 0.
2. For each day's price, each state either keeps its old value (do nothing today) or moves forward from the previous state: buying subtracts price, selling adds it.
3. Here we update in order using values from the same day, with no temporaries. That is safe because buying and selling on the same day changes the balance by 0, so it can never invent profit.
4. sell2 is the answer. It also covers making only one transaction (buy2 and sell2 on the same day add 0) or none at all.

Dry run on the example:

prices = [3, 3, 5, 0, 0, 3, 1, 4] (answer 6: buy at 0 sell at 3, buy at 1 sell at 4). Values at the end of each day:

day	price	buy1	sell1	buy2	sell2
start	—	−∞	0	−∞	0
0	3	-3	0	-3	0
1	3	-3	0	-3	0
2	5	-3	2	-3	2
3	0	0	2	2	2
4	0	0	2	2	2
5	3	0	3	2	5
6	1	0	3	2	5
7	4	0	4	2	6

Edge cases to test:

• Prices only fall → 0.
• One transaction is best.
• Very few days.

Complexity: O(n) time, O(1) space. It generalizes to k transactions with 2k states (LeetCode 188).

Problem: F(0) = 0, F(1) = 1, and F(n) = F(n − 1) + F(n − 2) for n > 1. Return F(n).

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 0 ≤ n ≤ 30

From brute force to the pattern: Direct recursion recomputes the same values exponentially often (O(2ⁿ)). Bottom-up DP is O(n) time and O(1) space.

Spot it: A recurrence where each value depends on smaller ones is DP's home ground. Plain recursion recomputes the same values exponentially often; building bottom-up computes each value once.

Approach:

1. Handle n < 2 directly: the answer is n.
2. Keep only the last two values: prev2 = F(i − 2), prev1 = F(i − 1).
3. For i = 2..n: current = prev1 + prev2, then slide the two variables forward.
4. Return prev1, which is now F(n).

class Solution:
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        prev2 = 0    # F(i - 2)
        prev1 = 1    # F(i - 1)
        for i in range(2, n + 1):
            current = prev1 + prev2
            # slide the window of the last two values forward
            prev2 = prev1
            prev1 = current
        return prev1

What the code is doing, line by line:

1. if n < 2: return n: F(0) = 0 and F(1) = 1 are the base cases.
2. prev2 = 0, prev1 = 1: we only ever need the last two values, so no array is needed (O(1) space).
3. current = prev1 + prev2: the recurrence.
4. prev2 = prev1, prev1 = current: shift both forward. The order matters: overwrite prev2 first, or its new value would be lost.
5. return prev1: after the loop, prev1 holds F(n).

Dry run on the example:

n = 5. Returns 5.

i	prev2	prev1	current = F(i)
2	0	1	1
3	1	1	2
4	1	2	3
5	2	3	5

Edge cases to test:

• n = 0 → 0.
• n = 1 → 1.
• n = 30 (too slow for plain recursion).

Complexity: O(n) time, O(1) space. (Naive recursion is O(2ⁿ); memoised recursion is O(n) time and space.)

Problem: cost[i] is the price of stepping on stair i. After paying you may climb 1 or 2 stairs. You may start on stair 0 or 1. Return the minimum cost to reach the top, just past the last stair.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 2 ≤ cost.length ≤ 1000 · 0 ≤ cost[i] ≤ 999

From brute force to the pattern: Trying every sequence of 1- and 2-steps is exponential. Each step's best cost depends only on the two below it: O(n).

Spot it: The cheapest way to reach a stair depends only on the cheapest ways to reach the two stairs below it, so this is 1-D DP. dp[i] = minimum cost to stand on stair i (not yet paid).

Approach:

1. dp[0] = dp[1] = 0: starting on either of the first two stairs is free.
2. For i = 2..n (where n is the top): you arrive from i − 1 (paying cost[i − 1]) or from i − 2 (paying cost[i − 2]).
3. dp[i] = min(dp[i − 1] + cost[i − 1], dp[i − 2] + cost[i − 2]).
4. Return dp[n].

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)              # stair n is the top (past the last stair)
        dp = [0] * (n + 1)         # dp[i] = cheapest way to stand on stair i
        # dp[0] = dp[1] = 0: you may start on stair 0 or 1 for free
        for i in range(2, n + 1):
            from_one_below = dp[i - 1] + cost[i - 1]
            from_two_below = dp[i - 2] + cost[i - 2]
            dp[i] = min(from_one_below, from_two_below)
        return dp[n]

What the code is doing, line by line:

1. dp = [0] * (n + 1): one entry per stair plus the top. Entries 0 and 1 stay 0.
2. from_one_below = dp[i - 1] + cost[i - 1]: stand on i − 1 as cheaply as possible, pay to leave it, take one step.
3. from_two_below: the same, from two stairs down.
4. dp[i] = min(...): the cheaper way in.
5. return dp[n]: the top. Only dp[i − 1] and dp[i − 2] are ever read, so two variables would also do.

Dry run on the example:

cost = [10, 15, 20] (LeetCode Example 1). Returns 15 (start on stair 1, pay 15, jump to the top).

i	from i−1	from i−2	dp[i]
2	0 + 15 = 15	0 + 10 = 10	10
3 (top)	10 + 20 = 30	0 + 15 = 15	15

Edge cases to test:

• Two steps.
• Starting on step 1 is cheaper.
• Expensive steps in the middle.

Complexity: O(n) time, O(n) space (O(1) with two variables).

Problem: Return the largest sum of any non-empty contiguous subarray of nums.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · -10⁴ ≤ nums[i] ≤ 10⁴

From brute force to the pattern: Summing every subarray is O(n²). Kadane's DP keeps only the best sum ending at each index: O(n) time, O(1) space.

Spot it: Define dp[i] = the best sum of a subarray that ends at i. It either extends the best subarray ending at i − 1 or starts fresh at i. That's Kadane's algorithm, a 1-D DP that needs only one variable.

Approach:

1. current = best sum of a subarray ending at the current index; best = the overall answer.
2. For each x: current = max(x, current + x). If the running sum went negative, it only drags x down, so start over at x.
3. best = max(best, current).

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        current = nums[0]     # best sum of a subarray ending at the current index
        best = nums[0]        # best sum seen anywhere
        for i in range(1, len(nums)):
            x = nums[i]
            # extend the previous subarray, or start a new one at x
            current = max(x, current + x)
            best = max(best, current)
        return best

What the code is doing, line by line:

1. current = nums[0], best = nums[0]: the subarray must be non-empty, so start from the first element (not 0, which would be wrong for an all-negative array).
2. current = max(x, current + x): if current is negative, current + x < x, so dropping the past is better.
3. best = max(best, current): the best subarray ends somewhere, so take the maximum over all ending positions.

Dry run on the example:

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] (LeetCode Example 1). Returns 6 (subarray [4, -1, 2, 1]).

x	current + x	current	best
-2	— (start)	-2	-2
1	-1	1 (restart)	1
-3	-2	-2	1
4	2	4 (restart)	4
-1	3	3	4
2	5	5	5
1	6	6	6
-5	1	1	6
4	5	5	6

Edge cases to test:

• All negative → the largest single element (don't start the answer at 0).
• A single element.
• Zeros in the array.

Complexity: O(n) time, O(1) space.

Problem: A robot starts at the top-left of an m × n grid and moves only right or down. How many distinct paths reach the bottom-right?

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ m, n ≤ 100

From brute force to the pattern: Enumerating every right/down path is exponential. Counting with a grid DP is O(m · n); the closed form is C(m + n − 2, m − 1).

Spot it: The last move into a cell comes from above or from the left, and those two sets of paths never overlap. So dp[r][c] = dp[r − 1][c] + dp[r][c − 1]: grid DP.

Approach:

1. Every cell in the first row and first column has exactly 1 path (straight right or straight down).
2. Fill the rest row by row: dp[r][c] = dp[r − 1][c] + dp[r][c − 1].
3. Return dp[m − 1][n − 1].

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # first row and first column: only one way to reach each cell
        dp = [[1] * n for _ in range(m)]
        for r in range(1, m):
            for c in range(1, n):
                # arrive from above or from the left
                dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
        return dp[m - 1][n - 1]

What the code is doing, line by line:

1. dp = [[1] * n for _ in range(m)]: a fresh row for each r (writing [[1] * n] * m would make every row the same list). The 1s in row 0 and column 0 are already correct.
2. for r in range(1, m): for c in range(1, n): row by row, so dp[r − 1][c] and dp[r][c − 1] are always ready.
3. dp[r][c] = dp[r - 1][c] + dp[r][c - 1]: add the two disjoint ways in.
4. return dp[m - 1][n - 1]: the bottom-right corner.

Dry run on the example:

m = 3, n = 7 (LeetCode Example 1). Returns 28. The finished table:

row	c=0	c=1	c=2	c=3	c=4	c=5	c=6
0	1	1	1	1	1	1	1
1	1	2	3	4	5	6	7
2	1	3	6	10	15	21	28

Edge cases to test:

• m = 1 or n = 1 → 1.
• A square grid.
• Large grids (watch overflow in other languages).

Complexity: O(m · n) time and space (one row is enough for O(n) space).

Problem: Same robot, but obstacleGrid[r][c] == 1 marks a blocked cell. Count the paths from the top-left to the bottom-right that avoid obstacles.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: m == obstacleGrid.length · n == obstacleGrid[i].length · 1 ≤ m, n ≤ 100 · obstacleGrid[i][j] is 0 or 1.

From brute force to the pattern: Enumerating paths is exponential. The grid DP stays O(r · c), with obstacles simply set to 0.

Spot it: Unique Paths with one change: no path can pass through an obstacle, so its count is 0. The first row and column are no longer all 1s either, because a block cuts off everything after it.

Approach:

1. dp[r][c] = number of paths to (r, c). If the start is blocked, the answer is 0.
2. Set dp[0][0] = 1, then visit cells row by row.
3. Obstacle → dp[r][c] = 0. Otherwise add the count from above (if r > 0) and from the left (if c > 0).
4. Return the bottom-right count.

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        rows = len(obstacleGrid)
        cols = len(obstacleGrid[0])
        dp = [[0] * cols for _ in range(rows)]
        if obstacleGrid[0][0] == 1:
            return 0
        dp[0][0] = 1
        for r in range(rows):
            for c in range(cols):
                if obstacleGrid[r][c] == 1:
                    dp[r][c] = 0               # nothing can pass through a rock
                    continue
                if r > 0:
                    dp[r][c] = dp[r][c] + dp[r - 1][c]   # from above
                if c > 0:
                    dp[r][c] = dp[r][c] + dp[r][c - 1]   # from the left
        return dp[rows - 1][cols - 1]

What the code is doing, line by line:

1. dp = [[0] * cols ...]: start every count at 0.
2. if obstacleGrid[0][0] == 1: return 0: a blocked start means no paths at all.
3. dp[0][0] = 1: one way to be at the start.
4. if obstacleGrid[r][c] == 1: dp[r][c] = 0; continue: an obstacle contributes nothing to its neighbours.
5. if r > 0 / if c > 0: add the counts from above and from the left when those cells exist. This also handles the first row and column without special cases (and (0, 0) keeps its 1).

Dry run on the example:

obstacleGrid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]] (LeetCode Example 1). Returns 2. The finished table (X = obstacle):

row	c=0	c=1	c=2
0	1	1	1
1	1	X (0)	1
2	1	1	2

Edge cases to test:

• The start or end cell is blocked → 0.
• An obstacle in the first row or column.
• A single cell.

Complexity: O(rows · cols) time and space.

Problem: Return the minimum path sum from the top of triangle to the bottom. From index i on one row you may move to index i or i + 1 on the row below.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ triangle.length ≤ 200 · triangle[0].length == 1 · triangle[i].length == triangle[i - 1].length + 1 · -10⁴ ≤ triangle[i][j] ≤ 10⁴

From brute force to the pattern: Trying every top-to-bottom path is O(2ⁿ). Paths share sub-paths, so bottom-up DP computes each cell once: O(n²) time, O(n) space.

Spot it: Choices that branch and re-merge (two parents share a child) → overlapping sub-problems → DP. Working from the bottom up, each cell needs only the two cells beneath it, and the answer ends up at the top.

Approach:

1. Copy the bottom row into best: from a bottom cell, the cheapest path is the cell itself.
2. For each row above, going up: best[i] = row[i] + min(best[i], best[i + 1]).
3. After the top row, best[0] is the answer.

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        # best[i] = cheapest path from (current row, i) down to the bottom
        best = list(triangle[-1])
        for r in range(len(triangle) - 2, -1, -1):
            row = triangle[r]
            for i in range(len(row)):
                # step to the cheaper of the two cells below
                best[i] = row[i] + min(best[i], best[i + 1])
        return best[0]

What the code is doing, line by line:

1. best = list(triangle[-1]): a copy of the bottom row, so the input is left unchanged.
2. for r in range(len(triangle) - 2, -1, -1): from the second-to-last row up to row 0.
3. best[i] = row[i] + min(best[i], best[i + 1]): best[i] and best[i + 1] still describe the row below, the two cells reachable from (r, i). Going left to right is safe because best[i + 1] hasn't been overwritten yet when we read it.
4. return best[0]: the top row has one cell.

Dry run on the example:

triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]] (LeetCode Example 1). Returns 11 (2 + 3 + 5 + 1).

row processed	best after
bottom [4, 1, 8, 3] (copied)	[4, 1, 8, 3]
[6, 5, 7]	[7, 6, 10] (+ unused tail)
[3, 4]	[9, 10] (+ unused tail)
[2]	[11] → 11

Edge cases to test:

• A single row.
• Negative numbers.
• The greedy choice (always the smaller child) fails, e.g. [[1], [2, 3], [9, 9, 0]].

Complexity: O(n²) time for n rows (every number once), O(n) extra space.

Problem: Letters map to 1..26. Count the ways to decode a digit string.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 100 · s contains only digits and may contain leading zero(s).

From brute force to the pattern: Recursing on both choices at every digit is exponential; the DP is linear.

Spot it: Each decoding of s[:i] ends with a 1-digit or 2-digit code → 1D DP, like climbing stairs with validity checks.

Why not another pattern? Recursion without memo branches twice per digit: exponential.

Approach:

1. prev2 = 1 (empty prefix), prev1 = ways for s[:1].
2. For each i: ways = (s[i−1] != '0' ? prev1 : 0) + (10 ≤ int(s[i−2:i]) ≤ 26 ? prev2 : 0).
3. Shift the window.

class Solution:
    def numDecodings(self, s: str) -> int:
        prev2 = 1  # ways to decode the empty prefix
        prev1 = 1 if s[0] != "0" else 0  # ways for s[:1]
        for i in range(2, len(s) + 1):
            cur = 0
            if s[i - 1] != "0":
                cur += prev1  # last letter uses one digit
            if 10 <= int(s[i - 2:i]) <= 26:
                cur += prev2  # last letter uses two digits
            prev2, prev1 = prev1, cur
        return prev1

What the code is doing, line by line:

1. A single digit decodes only if it isn't 0.
2. A pair decodes only in 10..26 (a leading 0 like 06 isn't allowed).
3. Only the last two counts are needed, so space is O(1).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Leading 0 → 0.
• "10", "20" (0 must pair).
• "30" → 0.

Complexity: O(n) time, O(1) space.

Problem: Is s3 formed by interleaving s1 and s2 (keeping each one's order)?

Solve it on LeetCode ↗

Constraints: 0 ≤ s1.length, s2.length ≤ 100 · 0 ≤ s3.length ≤ 200 · s1, s2, and s3 consist of lowercase English letters.

From brute force to the pattern: Trying both sources at each tie is exponential; the table has (m + 1)(n + 1) states.

Spot it: Using i characters of s1 and j of s2 fixes the position i + j in s3 → 2D DP. The last character of s3[:i+j] came from s1 or from s2.

Why not another pattern? Greedy (take from s1 when it matches) fails when both strings match the next character.

Approach:

1. If lengths don't add up, false.
2. dp[0][0] = True.
3. dp[i][j] = (dp[i−1][j] and s1[i−1] == s3[i+j−1]) or (dp[i][j−1] and s2[j−1] == s3[i+j−1]).

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n = len(s1), len(s2)
        if m + n != len(s3):
            return False
        dp = [[False] * (n + 1) for _ in range(m + 1)]  # dp[i][j]: s1[:i] + s2[:j] form s3[:i+j]
        dp[0][0] = True
        for i in range(m + 1):
            for j in range(n + 1):
                if i > 0 and dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]:
                    dp[i][j] = True  # last character taken from s1
                if j > 0 and dp[i][j - 1] and s2[j - 1] == s3[i + j - 1]:
                    dp[i][j] = True  # last character taken from s2
        return dp[m][n]

What the code is doing, line by line:

1. The state (i, j) determines exactly which prefix of s3 has been built.
2. Both sources are checked, which handles ties where s1 and s2 offer the same character.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Lengths don't add up → false.
• Empty strings.
• Repeated characters in both strings.

Complexity: O(m · n) time and space (a single row gives O(n) space).

Problem: Can s be split into a sequence of dictionary words (words reusable)?

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 300 · 1 ≤ wordDict.length ≤ 1000 · 1 ≤ wordDict[i].length ≤ 20 · s and wordDict[i] consist of only lowercase English letters. · All the strings of wordDict are unique.

From brute force to the pattern: Trying every split recursively is exponential (e.g. aaaa…ab); the prefix DP is polynomial.

Spot it: Whether a prefix can be segmented depends only on shorter prefixes → 1D DP: ok[i] is true if some word ends at i and the prefix before it is ok.

Why not another pattern? Backtracking on every split point re-solves the same suffixes exponentially often.

Approach:

1. ok[0] = True.
2. For each end i, for each word length L in the dictionary: if ok[i − L] and s[i − L:i] is a word, ok[i] = True.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        words = set(wordDict)
        lengths = set(map(len, words))
        ok = [False] * (len(s) + 1)  # ok[i]: s[:i] can be segmented
        ok[0] = True
        for i in range(1, len(s) + 1):
            for L in lengths:
                if L <= i and ok[i - L] and s[i - L:i] in words:
                    ok[i] = True  # a word ends here after a good prefix
                    break
        return ok[len(s)]

What the code is doing, line by line:

1. Only word lengths that actually occur need checking.
2. ok[i − L] says the part before the word is segmentable.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Words reused several times.
• No possible split.
• Overlapping candidate words (cats/cat).

Complexity: O(n · L · w) time where L is the number of distinct word lengths and w the word length (slicing); O(n) space.

Problem: Return the largest product of a non-empty contiguous subarray.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 2 * 10⁴ · -10 ≤ nums[i] ≤ 10 · The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

From brute force to the pattern: All subarrays: O(n²). Tracking max and min products: O(n).

Spot it: Like Kadane's algorithm, but a negative number turns the smallest product into the largest. So keep two DP values per position: max and min product of a subarray ending here.

Why not another pattern? Kadane with only a running maximum fails on [-2, 3, -4] (answer 24).

Approach:

1. hi = lo = best = nums[0].
2. For each x: candidates x, hi · x, lo · x; hi = max, lo = min of them.
3. best = max(best, hi).

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        hi = lo = best = nums[0]  # max / min product of a subarray ending here
        for x in nums[1:]:
            options = (x, hi * x, lo * x)  # start fresh, or extend either extreme
            hi = max(options)
            lo = min(options)  # a later negative can turn this into the max
            best = max(best, hi)
        return best

What the code is doing, line by line:

1. Starting fresh at x handles zeros and bad prefixes.
2. Multiplying by a negative swaps the roles of the largest and smallest products, so both are kept.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Zeros split the array.
• A single negative number.
• An even number of negatives.

Complexity: O(n) time, O(1) space.

Problem: In a binary matrix, return the area of the largest square containing only 1s.

Solve it on LeetCode ↗

Constraints: m == matrix.length · n == matrix[i].length · 1 ≤ m, n ≤ 300 · matrix[i][j] is '0' or '1'.

From brute force to the pattern: Checking every square from every corner is O(m · n · min(m,n)²). The DP is O(mn).

Spot it: The largest square with bottom-right corner (r, c) is limited by the squares ending at its top, left and top-left neighbours → 2D DP: 1 + min(of the three).

Why not another pattern? Growing a square from every cell is O((mn)²).

Approach:

1. side[r][c] = 0 for a '0'.
2. Otherwise side[r][c] = 1 + min(side[r−1][c], side[r][c−1], side[r−1][c−1]).
3. Answer: max(side)².

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        side = [[0] * (n + 1) for _ in range(m + 1)]  # side[r+1][c+1]: biggest square ending at (r, c)
        best = 0
        for r in range(m):
            for c in range(n):
                if matrix[r][c] == "1":
                    side[r + 1][c + 1] = 1 + min(side[r][c + 1], side[r + 1][c], side[r][c])  # limited by all three
                    best = max(best, side[r + 1][c + 1])
        return best * best

What the code is doing, line by line:

1. A square of side s ending at (r, c) needs squares of side s − 1 ending above, left and diagonally.
2. The padding row/column of zeros avoids boundary checks.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No 1s → 0.
• All 1s → min(m,n)².
• One row.

Complexity: O(m · n) time and space.

Problem: Split n ≥ 2 into at least two positive integers to maximise their product.

Solve it on LeetCode ↗

Constraints: 2 ≤ n ≤ 58

From brute force to the pattern: Enumerating partitions is exponential; the DP is O(n²).

Spot it: The best product for i uses a first part j and then either keeps i − j whole or splits it further (its own best) → 1D DP like unbounded knapsack.

Why not another pattern? Trying every partition of n is exponential (partition numbers grow fast).

Approach:

1. best[1] = 1.
2. For i from 2 to n: best[i] = max(j · max(i − j, best[i − j])) over j in 1..i − 1.

class Solution:
    def integerBreak(self, n: int) -> int:
        best = [0] * (n + 1)  # best[i]: max product splitting i into at least two parts
        best[1] = 1
        for i in range(2, n + 1):
            for j in range(1, i):
                best[i] = max(best[i], j * max(i - j, best[i - j]))  # keep the rest whole or split it
        return best[n]

What the code is doing, line by line:

1. max(i − j, best[i − j]) allows the rest to stay whole, since best itself forces at least two parts.
2. The math shortcut is to use as many 3s as possible, but the DP explains why without proof.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n = 2 → 1.
• n = 3 → 2.
• n = 4 → 4.

Complexity: O(n²) time, O(n) space.

Problem: Return a largest subset where every pair (a, b) satisfies a % b == 0 or b % a == 0.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 1000 · 1 ≤ nums[i] ≤ 2 * 10⁹ · All the integers in nums are unique.

From brute force to the pattern: Trying all subsets is O(2ⁿ · n²). The chain DP is O(n²).

Spot it: After sorting, a divisible subset is a chain where each element divides the next (divisibility is transitive). That's Longest Increasing Subsequence with nums[i] % nums[j] == 0 as the link.

Why not another pattern? Checking all subsets is O(2ⁿ).

Approach:

1. Sort. size[i] = longest chain ending at i; parent[i] = previous element.
2. For each j < i with nums[i] % nums[j] == 0: extend if size[j] + 1 is bigger.
3. Rebuild from the index with the largest size.

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums = sorted(nums)
        n = len(nums)
        size = [1] * n  # longest divisible chain ending at i
        parent = [-1] * n
        for i in range(n):
            for j in range(i):
                if nums[i] % nums[j] == 0 and size[j] + 1 > size[i]:
                    size[i] = size[j] + 1  # nums[j] divides nums[i]: extend its chain
                    parent[i] = j
        i = max(range(n), key=lambda t: size[t])
        subset = []
        while i != -1:
            subset.append(nums[i])  # walk the chain backwards
            i = parent[i]
        return subset[::-1]

What the code is doing, line by line:

1. If a | b and b | c then a | c, so checking only consecutive chain elements is enough.
2. This is the O(n²) LIS DP with a different link condition.
3. Parent pointers rebuild one optimal chain.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A single element.
• Several answers of the same size (any is accepted).
• 1 divides everything.

Complexity: O(n²) time, O(n) space.

Problem: Count ordered sequences of numbers from nums (reusable) that add up to target.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 200 · 1 ≤ nums[i] ≤ 1000 · All the elements of nums are unique. · 1 ≤ target ≤ 1000

From brute force to the pattern: Listing every sequence is exponential. The DP is O(target · n).

Spot it: Sequences, not sets: different orders count separately. The last number of the sequence is any x, leaving t − x → 1D DP over the total with the target in the outer loop.

Why not another pattern? Coin Change II's loop order (coins outside) counts combinations, not sequences.

Approach:

1. ways[0] = 1.
2. For t from 1 to target: ways[t] = Σ ways[t − x] over x ≤ t.

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        ways = [0] * (target + 1)
        ways[0] = 1  # the empty sequence
        for t in range(1, target + 1):  # totals outside: every order is counted
            for x in nums:
                if x <= t:
                    ways[t] += ways[t - x]  # sequences ending with x
        return ways[target]

What the code is doing, line by line:

1. Classifying sequences by their last number gives each sequence exactly once.
2. Putting the total in the outer loop allows any number at any position, which is why orders count separately.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No way to reach target → 0.
• target smaller than all numbers.
• One number.

Complexity: O(target · n) time, O(target) space.

Problem: F(k) = Σ i · arrₖ[i] where arrₖ is nums rotated right by k. Return the maximum F(k).

Solve it on LeetCode ↗

Constraints: n == nums.length · 1 ≤ n ≤ 10⁵ · -100 ≤ nums[i] ≤ 100

From brute force to the pattern: Computing every F(k) directly is O(n²); the recurrence is O(n).

Spot it: Computing each F(k) from scratch is O(n²). Each rotation adds 1 to every coefficient (adding sum) except the last element, which drops from n − 1 to 0 (subtracting n · that element). A recurrence from one state to the next.

Why not another pattern? Direct evaluation of all n rotations is O(n²).

Approach:

1. F = Σ i · nums[i], total = sum(nums).
2. For k = 1..n − 1: F += total − n · nums[n − k].
3. Track the maximum.

class Solution:
    def maxRotateFunction(self, nums: List[int]) -> int:
        n = len(nums)
        total = sum(nums)
        f = sum(i * x for i, x in enumerate(nums))  # F(0)
        best = f
        for k in range(1, n):
            f += total - n * nums[n - k]  # everyone shifts right; the last element wraps to index 0
            best = max(best, f)
        return best

What the code is doing, line by line:

1. Rotating right moves every element one index up (adding its value once more), so F grows by total.
2. The element at the end wraps to index 0: it had coefficient n − 1, now 0, a loss of n · value after the total was added.
3. In rotation k the wrapping element is nums[n − k].

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• One element → 0.
• Negative numbers.
• All equal values.

Complexity: O(n) time, O(1) space.

Problem: Players alternately take a number from either end. Does player 1 win (ties count as a win) with optimal play?

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 20 · 0 ≤ nums[i] ≤ 10⁷

From brute force to the pattern: Exploring the full game tree is O(2ⁿ); the interval DP is O(n²).

Spot it: A two-player game on an interval → interval DP with the score difference: the player to move on nums[i..j] takes one end and then faces the opponent's best difference on what's left.

Why not another pattern? Greedy (take the bigger end) loses on cases like [1, 5, 2] vs [1, 5, 233, 7].

Approach:

1. diff[i][i] = nums[i].
2. diff[i][j] = max(nums[i] − diff[i+1][j], nums[j] − diff[i][j−1]).
3. Player 1 wins if diff[0][n−1] ≥ 0.

class Solution:
    def predictTheWinner(self, nums: List[int]) -> bool:
        n = len(nums)
        diff = [[0] * n for _ in range(n)]  # diff[i][j]: mover's score minus opponent's on nums[i..j]
        for i in range(n - 1, -1, -1):
            diff[i][i] = nums[i]
            for j in range(i + 1, n):
                take_left = nums[i] - diff[i + 1][j]  # opponent then plays optimally on the rest
                take_right = nums[j] - diff[i][j - 1]
                diff[i][j] = max(take_left, take_right)
        return diff[0][n - 1] >= 0

What the code is doing, line by line:

1. Using the difference removes the need to track whose turn it is: the opponent's best difference is subtracted.
2. Rows go from the bottom up so diff[i + 1][j] is ready before diff[i][j].

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• One number → true.
• A tie → true.
• An even count (player 1 can always at least tie).

Complexity: O(n²) time and space.

Problem: Put + or − before each number; count the expressions that evaluate to target.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 20 · 0 ≤ nums[i] ≤ 1000 · 0 ≤ sum(nums[i]) ≤ 1000 · -1000 ≤ target ≤ 1000

From brute force to the pattern: Enumerating all 2ⁿ sign patterns is exponential; merging equal sums makes it O(n · S).

Spot it: After processing some numbers, only the running sum matters → DP over sums (a hash map from sum to number of ways). Equivalently a 0/1 knapsack: choose the positive set P with sum(P) = (total + target) / 2.

Why not another pattern? Trying all 2ⁿ sign choices is too slow for n = 20 in many languages and doesn't scale.

Approach:

1. ways = {0: 1}.
2. For each number x: new map with s + x and s − x for every s, adding counts.
3. Return ways[target].

from collections import defaultdict

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        ways = {0: 1}  # running sum -> number of sign choices giving it
        for x in nums:
            nxt = defaultdict(int)
            for s, count in ways.items():
                nxt[s + x] += count  # put + before x
                nxt[s - x] += count  # put - before x
            ways = nxt
        return ways.get(target, 0)

What the code is doing, line by line:

1. Different sign choices that reach the same sum are merged, so the state space is bounded by the range of sums.
2. Zeros double the count (both signs give the same sum), which the map handles naturally.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Zeros (both signs count).
• Unreachable target → 0.
• Negative target.

Complexity: O(n · S) time and space, where S is the range of possible sums (≤ 2·sum + 1).

Problem: Return the length of the longest palindromic subsequence of s.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 1000 · s consists only of lowercase English letters.

From brute force to the pattern: All subsequences: O(2ⁿ). Interval DP: O(n²).

Spot it: A palindrome is decided by its outer pair, then its inside → interval DP on s[i..j]. Equal ends both join; different ends mean one of them isn't used.

Why not another pattern? Checking all 2ⁿ subsequences is impossible; it also equals LCS(s, reversed s) but the interval form is direct.

Approach:

1. L[i][i] = 1.
2. s[i] == s[j]: L[i][j] = L[i+1][j−1] + 2; else max(L[i+1][j], L[i][j−1]).

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        L = [[0] * n for _ in range(n)]  # L[i][j]: longest palindromic subsequence in s[i..j]
        for i in range(n - 1, -1, -1):
            L[i][i] = 1
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    L[i][j] = L[i + 1][j - 1] + 2  # both ends wrap the inside
                else:
                    L[i][j] = max(L[i + 1][j], L[i][j - 1])  # one end can't be used
        return L[0][n - 1]

What the code is doing, line by line:

1. Rows from bottom to top make L[i + 1][…] ready first.
2. When j = i + 1 and the characters match, L[i + 1][j − 1] is the empty range (0).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All same letters → n.
• All distinct → 1.
• Length 1.

Complexity: O(n²) time and space.

Problem: Return the minimum number of deletions (in either string) to make word1 and word2 equal.

Solve it on LeetCode ↗

Constraints: 1 ≤ word1.length, word2.length ≤ 500 · word1 and word2 consist of only lowercase English letters.

From brute force to the pattern: Trying all subsets to delete is exponential; LCS is O(mn).

Spot it: What remains in both strings is a common subsequence; to delete least, keep the longest one → LCS DP.

Why not another pattern? Edit distance with replacements gives a different (smaller) number; only deletions are allowed here.

Approach:

1. LCS table: L[i][j] = L[i−1][j−1] + 1 if chars match else max(L[i−1][j], L[i][j−1]).
2. Answer: m + n − 2 · L[m][n].

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        L = [[0] * (n + 1) for _ in range(m + 1)]  # L[i][j]: LCS of word1[:i], word2[:j]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    L[i][j] = L[i - 1][j - 1] + 1  # keep this common letter
                else:
                    L[i][j] = max(L[i - 1][j], L[i][j - 1])
        return m + n - 2 * L[m][n]  # delete everything outside the LCS

What the code is doing, line by line:

1. The final common string must be a subsequence of both words.
2. Keeping the LCS minimises the letters deleted from each side.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No common letters → m + n.
• Equal words → 0.
• One empty word.

Complexity: O(m · n) time and space.

Problem: Buy exactly the needed quantities of up to 6 items using single prices and bundle offers. Return the minimum cost.

Solve it on LeetCode ↗

Constraints: n == price.length == needs.length · 1 ≤ n ≤ 6 · 0 ≤ price[i], needs[i] ≤ 10 · 1 ≤ special.length ≤ 100 · special[i].length == n + 1 · 0 ≤ special[i][j] ≤ 50 · The input is generated that at least one of special[i][j] is non-zero for 0 ≤ j ≤ n - 1.

From brute force to the pattern: Trying every sequence of offers without memo repeats states; the memo bounds the work by the number of need vectors.

Spot it: The state is the vector of remaining needs (small: ≤ 6 items, ≤ 10 each) → memoised DP over tuples. From a state, either pay full price for everything or apply an offer that fits and recurse.

Why not another pattern? Greedy (best discount first) fails because offers interact.

Approach:

1. cost(needs): start with buying everything at single prices.
2. For each offer that doesn't exceed any need: offer price + cost(needs − offer).
3. Memoise on the needs tuple.

from functools import lru_cache

class Solution:
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
        n = len(price)

        @lru_cache(maxsize=None)
        def cost(needs):
            best = sum(p * q for p, q in zip(price, needs))  # no offers: buy singly
            for offer in special:
                rest = tuple(needs[i] - offer[i] for i in range(n))
                if min(rest) >= 0:  # the offer doesn't give more than needed
                    best = min(best, offer[n] + cost(rest))
            return best

        return cost(tuple(needs))

What the code is doing, line by line:

1. Each state is a tuple, so it can be a cache key.
2. Offers that would overshoot any item are skipped (buying extra isn't allowed).
3. The number of states is at most 11⁶, and much less in practice.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• An offer more expensive than buying singly.
• No offer fits.
• Needs all zero → 0.

Complexity: O(S · offers · n) time, where S is the number of reachable needs vectors.

Problem: Count the substrings of s that are palindromes.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 1000 · s consists of lowercase English letters.

From brute force to the pattern: Testing every substring is O(n³); centre expansion is O(n²).

Spot it: A palindrome grows from its centre: s[l..r] is one if s[l+1..r−1] is and s[l] == s[r]. Expanding around every centre applies that DP relation without a table.

Why not another pattern? Checking each of the O(n²) substrings separately is O(n³).

Approach:

1. For each centre (a character, or a gap between two): l, r start there.
2. While s[l] == s[r]: count one, expand outwards.

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        count = 0
        for center in range(2 * n - 1):  # n letters and n - 1 gaps
            l = center // 2
            r = l + center % 2
            while l >= 0 and r < n and s[l] == s[r]:
                count += 1  # s[l..r] is a palindrome
                l -= 1
                r += 1
        return count

What the code is doing, line by line:

1. Even center values are letters (odd-length palindromes); odd values are gaps (even length).
2. Every expansion step is a new palindrome with the same centre.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All equal letters → n(n + 1)/2.
• All distinct → n.
• Single character.

Complexity: O(n²) time, O(1) space.

Problem: Return how many longest strictly increasing subsequences there are.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 2000 · -10⁶ ≤ nums[i] ≤ 10⁶ · The answer is guaranteed to fit inside a 32-bit integer.

From brute force to the pattern: Listing every increasing subsequence is exponential; the counting DP is O(n²).

Spot it: The O(n²) LIS DP extended with counts: length[i] and count[i] for subsequences ending at i. A longer extension resets the count; an equally long one adds to it.

Why not another pattern? The patience-sorting O(n log n) LIS gives the length but not the count without extra structure.

Approach:

1. length[i] = count[i] = 1.
2. For j < i with nums[j] < nums[i]: if length[j] + 1 > length[i], take it and copy count[j]; if equal, add count[j].
3. Sum count[i] over indices with the maximum length.

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        length = [1] * n  # longest increasing subsequence ending at i
        count = [1] * n  # how many of that length end at i
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if length[j] + 1 > length[i]:
                        length[i] = length[j] + 1  # a longer one: restart the count
                        count[i] = count[j]
                    elif length[j] + 1 == length[i]:
                        count[i] += count[j]  # another way to the same length
        top = max(length)
        return sum(c for l, c in zip(length, count) if l == top)

What the code is doing, line by line:

1. count[i] counts distinct index sequences, matching the problem's definition.
2. The final answer adds the counts over every possible ending index.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All equal → n (each element alone).
• Strictly increasing → 1.
• Decreasing → n.

Complexity: O(n²) time, O(n) space.

Problem: Unlimited transactions, each costing fee. Return the maximum profit.

Solve it on LeetCode ↗

Constraints: 1 ≤ prices.length ≤ 5 * 10⁴ · 1 ≤ prices[i] < 5 * 10⁴ · 0 ≤ fee < 5 * 10⁴

From brute force to the pattern: Trying all buy/sell day choices is exponential; two states per day is O(n).

Spot it: Each day you either hold a share or don't → two-state DP. Selling moves hold → cash and pays the fee.

Why not another pattern? Adding every price rise (unlimited transactions without fee) pays the fee on each small rise.

Approach:

1. cash = 0, hold = −prices[0].
2. Each day: cash = max(cash, hold + p − fee), hold = max(hold, cash − p).

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        cash = 0  # best balance with no share
        hold = -prices[0]  # best balance holding a share
        for p in prices[1:]:
            cash = max(cash, hold + p - fee)  # sell today (pay the fee)
            hold = max(hold, cash - p)  # buy today
        return cash

What the code is doing, line by line:

1. Using the updated cash for hold on the same day only allows sell-then-buy on one day, which never helps, so it's safe.
2. The fee makes merging nearby rises into one transaction better, which the DP finds automatically.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Fee larger than any rise → 0.
• Falling prices → 0.
• One day.

Complexity: O(n) time, O(1) space.

Problem: Taking a number x earns x but deletes every x − 1 and x + 1. Return the maximum points.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 2 * 10⁴ · 1 ≤ nums[i] ≤ 10⁴

From brute force to the pattern: Trying every subset of values is exponential; the House Robber DP is linear in the value range.

Spot it: If you take one x, take them all. Sum points per value: points[x] = x · count(x). Taking x forbids x − 1 and x + 1, which is exactly House Robber on the value line.

Why not another pattern? Greedy (take the biggest total first) fails when two neighbours together beat the middle value.

Approach:

1. points[v] = v · count(v) for v up to max(nums).
2. House Robber: take, skip running values; take = skip + points[v], skip = max(previous take, previous skip).

from collections import Counter

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        count = Counter(nums)
        take = skip = 0  # best total when value v-1 is taken / not taken
        for v in range(1, max(nums) + 1):
            gain = v * count[v]  # take every copy of v
            take, skip = skip + gain, max(take, skip)  # taking v needs v-1 skipped
        return max(take, skip)

What the code is doing, line by line:

1. Taking one copy of x already deletes all x ± 1, so the other copies of x are free to take too.
2. Values form a line where neighbours conflict: House Robber.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Values with gaps (no conflict).
• All the same value.
• One number.

Complexity: O(n + max) time, O(n) space for the counter.

Problem: A number is good if rotating each digit 180° gives a valid, different number. Count good numbers in 1..n.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 10⁴

From brute force to the pattern: Examining every digit of every number is O(n log n); prefix reuse makes it O(n) (digit DP gives O(log n)).

Spot it: Digits 0, 1, 8 rotate to themselves; 2, 5, 6, 9 change; 3, 4, 7 break the number. A number's status follows from i // 10's status and its last digit → DP over numbers (a simple digit DP).

Why not another pattern? Checking each number's digits separately is O(n log n); reusing the prefix status is O(n).

Approach:

1. state[i]: 0 = invalid, 1 = valid and unchanged, 2 = valid and changed. state[0] = 1.
2. state[i] = invalid if the last digit is 3/4/7 or the prefix is invalid; changed if either is changed; else unchanged.
3. Count i ≤ n with state[i] == 2.

class Solution:
    def rotatedDigits(self, n: int) -> int:
        kind = {0: 1, 1: 1, 8: 1, 2: 2, 5: 2, 6: 2, 9: 2, 3: 0, 4: 0, 7: 0}  # 0 bad, 1 same, 2 changes
        state = [0] * (n + 1)
        state[0] = 1
        good = 0
        for i in range(1, n + 1):
            prefix, last = state[i // 10], kind[i % 10]
            if prefix == 0 or last == 0:
                state[i] = 0  # contains 3, 4 or 7
            else:
                state[i] = max(prefix, last)  # changed if any digit changes
            if state[i] == 2:
                good += 1
        return good

What the code is doing, line by line:

1. i // 10 is i without its last digit, already computed.
2. Using 0 < 1 < 2 for bad < same < changed makes max the right combination once both parts are valid.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n < 2 → 0.
• Numbers made only of 0/1/8 (valid but unchanged).
• Any 3/4/7 digit.

Complexity: O(n) time and space.

Problem: Count tilings of a 2 × n board with dominoes and L-trominoes (mod 10⁹ + 7).

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 1000

From brute force to the pattern: Enumerating tilings is exponential; two states per column make it linear.

Spot it: Tile column by column. Besides a flat edge, a tromino can leave one cell sticking out, so track two states: full[i] (first i columns covered) and half[i] (first i columns plus one cell of column i + 1; top and bottom are mirror images, so count one and double it) → DP with profile states.

Why not another pattern? Counting with dominoes only (Fibonacci) misses tromino pairs that span several columns.

Approach:

1. full[0] = full[1] = 1, half[0] = 0, half[1] = 1.
2. full[i] = full[i−1] (vertical domino) + full[i−2] (two horizontal dominoes) + 2 · half[i−2] (a tromino fills the gap and column i).
3. half[i] = full[i−1] (a tromino covers column i and sticks out) + half[i−1] (a horizontal domino fills the gap and sticks out).

class Solution:
    def numTilings(self, n: int) -> int:
        MOD = 10**9 + 7
        full = [0] * (n + 1)  # columns 1..i fully covered
        half = [0] * (n + 1)  # columns 1..i covered plus one cell of column i+1 (one orientation)
        full[0] = 1
        full[1] = 1
        half[1] = 1  # a tromino covering column 1 and one cell of column 2
        for i in range(2, n + 1):
            full[i] = (full[i - 1] + full[i - 2] + 2 * half[i - 2]) % MOD  # domino, two dominoes, or a closing tromino
            half[i] = (full[i - 1] + half[i - 1]) % MOD  # open with a tromino, or extend with a domino
        return full[n]

What the code is doing, line by line:

1. The jagged edge has two mirror images (top or bottom cell sticking out); half counts one and the factor 2 covers both.
2. From a jagged state ending at column i − 2 with one cell in column i − 1, a tromino covers the other cell of i − 1 and all of column i.
3. A jagged state is created by a tromino on a flat edge, or carried forward by a horizontal domino in the empty row.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n = 1 → 1.
• n = 2 → 2.
• n = 3 → 5 (includes tromino pairs).

Complexity: O(n) time (O(1) space if only the last values are kept).

Problem: Pour poured cups on the top glass of a pyramid; overflow splits equally to the two glasses below. How full is glass (query_row, query_glass)?

Solve it on LeetCode ↗

Constraints: 0 ≤ poured ≤ 10⁹ · 0 ≤ query_glass ≤ query_row < 100

From brute force to the pattern: Pouring one cup at a time and simulating is slower and unnecessary. Row DP is O(rows²).

Spot it: Flow only goes down, so each row depends on the row above → row-by-row DP of how much liquid passes through each glass.

Why not another pattern? Simulating cup by cup over time is unnecessary; only the total flow through each glass matters.

Approach:

1. row = [poured].
2. For each next row: every glass with x > 1 sends (x − 1) / 2 to each child.
3. Return min(1, row[query_glass]).

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        row = [float(poured)]  # total liquid that reaches each glass of the current row
        for r in range(query_row):
            nxt = [0.0] * (r + 2)
            for i, x in enumerate(row):
                extra = max(0.0, x - 1) / 2  # the glass keeps 1 cup; the rest splits
                nxt[i] += extra
                nxt[i + 1] += extra
            row = nxt
        return min(1.0, row[query_glass])

What the code is doing, line by line:

1. The value stored is the total that flows into a glass, which may exceed 1.
2. Only the excess over 1 is shared, half to each child.
3. The answer is capped at 1, a full glass.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• poured = 0.
• A glass at the edge of a row (one parent).
• Huge poured (cap at 1).

Complexity: O(query_row²) time, O(query_row) space.

Problem: Even number of piles, odd total; players take a pile from either end. Does Alice (first) win with optimal play?

Solve it on LeetCode ↗

Constraints: 2 ≤ piles.length ≤ 500 · piles.length is even. · 1 ≤ piles[i] ≤ 500 · sum(piles[i]) is odd.

From brute force to the pattern: The full game tree is O(2ⁿ); interval DP is O(n²).

Spot it: Same game as Predict the Winner → interval DP on the score difference. (There's also a proof: Alice can choose to take all even-indexed or all odd-indexed piles, and one of those sums is larger, so she always wins.)

Why not another pattern? Greedy (take the larger end) isn't optimal; return True is correct but the DP shows why.

Approach:

1. diff[i][j] = best (mover − other) on piles i..j.
2. diff[i][j] = max(piles[i] − diff[i+1][j], piles[j] − diff[i][j−1]).
3. Return diff[0][n−1] > 0.

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        diff = [[0] * n for _ in range(n)]  # mover's lead on piles[i..j]
        for i in range(n - 1, -1, -1):
            diff[i][i] = piles[i]
            for j in range(i + 1, n):
                diff[i][j] = max(piles[i] - diff[i + 1][j], piles[j] - diff[i][j - 1])  # take an end
        return diff[0][n - 1] > 0

What the code is doing, line by line:

1. Each choice gives the opponent the remaining interval, where they get their own best lead.
2. The total is odd, so there are no ties; a positive lead means Alice wins.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Two piles.
• Large middle pile.
• Alternating big and small piles.

Complexity: O(n²) time and space.

Problem: Return the maximum sum of a non-empty subarray of a circular array.

Solve it on LeetCode ↗

Constraints: n == nums.length · 1 ≤ n ≤ 3 * 10⁴ · -3 * 10⁴ ≤ nums[i] ≤ 3 * 10⁴

From brute force to the pattern: Kadane from every starting point is O(n²); the complement trick is O(n).

Spot it: A wrapping subarray is the whole array minus a middle subarray, so its best sum is total − (minimum subarray). Run Kadane's DP for both the max and the min.

Why not another pattern? Trying every start point with Kadane is O(n²).

Approach:

1. Kadane for the maximum subarray and for the minimum subarray, in one pass.
2. If the max is negative (all numbers negative), return it.
3. Otherwise return max(max_sub, total − min_sub).

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        cur_max = cur_min = 0
        best_max = float("-inf")
        best_min = float("inf")
        for x in nums:
            cur_max = max(cur_max + x, x)  # best subarray ending here
            cur_min = min(cur_min + x, x)  # worst subarray ending here
            best_max = max(best_max, cur_max)
            best_min = min(best_min, cur_min)
        if best_max < 0:
            return best_max  # all negative: removing the min would leave nothing
        return max(best_max, sum(nums) - best_min)  # normal, or wrapping around

What the code is doing, line by line:

1. A wrapping subarray leaves out one contiguous middle part; leaving out the smallest one gives the biggest wrap.
2. If every number is negative, total − min would be the empty subarray (0), which isn't allowed.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All negative.
• All positive (the whole array).
• One element.

Complexity: O(n) time, O(1) space.

Problem: A falling path takes one cell per row, moving to the same or an adjacent column. Return the minimum path sum.

Solve it on LeetCode ↗

Constraints: n == matrix.length == matrix[i].length · 1 ≤ n ≤ 100 · -100 ≤ matrix[i][j] ≤ 100

From brute force to the pattern: All 3ⁿ paths vs an O(n²) row DP.

Spot it: The best path to a cell comes from one of the three cells above → row-by-row DP.

Why not another pattern? Trying all paths is O(3ⁿ).

Approach:

1. prev = first row.
2. Each next row: cur[c] = matrix[r][c] + min(prev[c − 1], prev[c], prev[c + 1]) (within bounds).
3. Answer: min(prev) after the last row.

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        prev = matrix[0][:]  # best path sum ending at each cell of the previous row
        for r in range(1, n):
            cur = [0] * n
            for c in range(n):
                above = prev[max(0, c - 1):c + 2]  # up-left, up, up-right
                cur[c] = matrix[r][c] + min(above)
            prev = cur
        return min(prev)

What the code is doing, line by line:

1. The slice prev[max(0, c − 1):c + 2] handles both edges.
2. Only the previous row is needed.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• 1×1 matrix.
• Negative values.
• Edge columns (two parents).

Complexity: O(n²) time, O(n) space.

Problem: Travel days are given; passes cost costs[0] (1 day), costs[1] (7 days), costs[2] (30 days). Return the minimum cost.

Solve it on LeetCode ↗

Constraints: 1 ≤ days.length ≤ 365 · 1 ≤ days[i] ≤ 365 · days is in strictly increasing order. · costs.length == 3 · 1 ≤ costs[i] ≤ 1000

From brute force to the pattern: Trying every combination of passes is exponential; the day DP is O(365).

Spot it: The cheapest cover for days 1..d ends with a pass that covers day d → 1D DP over calendar days.

Why not another pattern? Greedy (buy a 7-day pass when many trips are close) misjudges overlaps; the DP checks all three choices.

Approach:

1. cost[0] = 0.
2. Day d not a travel day: cost[d] = cost[d − 1].
3. Otherwise: min(cost[d−1] + c1, cost[max(0, d−7)] + c7, cost[max(0, d−30)] + c30).

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        travel = set(days)
        last = days[-1]
        cost = [0] * (last + 1)  # cost[d]: cheapest way to cover travel days up to d
        for d in range(1, last + 1):
            if d not in travel:
                cost[d] = cost[d - 1]  # nothing to cover today
                continue
            cost[d] = min(cost[d - 1] + costs[0],  # 1-day pass for today
                          cost[max(0, d - 7)] + costs[1],  # 7-day pass ending today
                          cost[max(0, d - 30)] + costs[2])  # 30-day pass ending today
        return cost[last]

What the code is doing, line by line:

1. A pass bought to cover day d can be assumed to end on day d, covering the days before it.
2. Non-travel days cost nothing extra.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A 7-day pass cheaper than a 1-day pass.
• One travel day.
• Travel every day for a month.

Complexity: O(last day) time and space (≤ 365).

Problem: Split the array into blocks of length ≤ k; each block becomes its maximum. Return the largest possible sum.

Solve it on LeetCode ↗

Constraints: 1 ≤ arr.length ≤ 500 · 0 ≤ arr[i] ≤ 10⁹ · 1 ≤ k ≤ arr.length

From brute force to the pattern: All partitions: O(2ⁿ). DP: O(nk).

Spot it: The last block of the prefix arr[:i] has length 1..k → 1D DP over prefixes, tracking the block max while extending it leftwards.

Why not another pattern? Greedy blocks around big values can be wrong; all splits are O(2ⁿ).

Approach:

1. best[0] = 0.
2. For i = 1..n: for L = 1..min(k, i): top = max(top, arr[i − L]); best[i] = max(best[i], best[i − L] + top · L).

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        best = [0] * (n + 1)  # best[i]: answer for arr[:i]
        for i in range(1, n + 1):
            top = 0
            for L in range(1, min(k, i) + 1):  # the last block is arr[i-L:i]
                top = max(top, arr[i - L])
                best[i] = max(best[i], best[i - L] + top * L)
        return best[n]

What the code is doing, line by line:

1. Growing the last block one element to the left updates its maximum in O(1).
2. Every block of the last partition is considered, so the best is found.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k = 1 → the sum.
• k = n → n · max.
• One element.

Complexity: O(n · k) time, O(n) space.

Problem: A word is a predecessor of another if inserting one letter makes it. Return the longest chain length.

Solve it on LeetCode ↗

Constraints: 1 ≤ words.length ≤ 1000 · 1 ≤ words[i].length ≤ 16 · words[i] only consists of lowercase English letters.

From brute force to the pattern: Comparing every pair of words is O(n² · L); generating deletions is O(n · L²).

Spot it: Chains grow by one letter, so process words by length. A word's best chain is 1 + the best among the words obtained by deleting one letter → DP with a hash map.

Why not another pattern? Checking every pair of words for the predecessor relation is O(n² · L).

Approach:

1. Sort words by length.
2. For each word, try deleting each position; chain[word] = max(chain.get(shorter, 0) + 1).
3. Return the max chain.

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        chain = {}  # word -> longest chain ending with it
        for w in sorted(words, key=len):  # shorter words first
            best = 1
            for i in range(len(w)):
                shorter = w[:i] + w[i + 1:]  # delete one letter
                if shorter in chain:
                    best = max(best, chain[shorter] + 1)
            chain[w] = best
        return max(chain.values())

What the code is doing, line by line:

1. Deleting letters from the longer word generates its only possible predecessors (L of them).
2. Sorting by length guarantees predecessors are already processed.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Duplicate words.
• No chains → 1.
• Several chains of the same length.

Complexity: O(n · L²) time (L deletions, each O(L)), O(n · L) space.

Problem: Smashing stones x ≤ y leaves y − x. Return the smallest possible final weight.

Solve it on LeetCode ↗

Constraints: 1 ≤ stones.length ≤ 30 · 1 ≤ stones[i] ≤ 100

From brute force to the pattern: All sign assignments: O(2ⁿ). Subset sums: O(n · total).

Spot it: Every final result is |sum(A) − sum(B)| for some split into two groups (signs + and −). Minimise it by finding the subset sum closest to total / 2 → subset-sum DP.

Why not another pattern? Simulating smashes greedily (largest two) is the easier problem 1046 and isn't optimal here.

Approach:

1. sums = {0}; for each stone, add s + stone for every reachable s ≤ total / 2.
2. Answer: total − 2 · max(sums).

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total = sum(stones)
        sums = {0}  # subset sums reachable so far (only up to half the total)
        for x in stones:
            sums |= {s + x for s in sums if s + x <= total // 2}
        return total - 2 * max(sums)  # the two groups as even as possible

What the code is doing, line by line:

1. Each smash subtracts one group from another, so the end weight is a signed sum of the stones.
2. The best split has one group as close to total / 2 as possible from below.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• One stone → its weight.
• Two equal stones → 0.
• Total is odd (answer ≥ 1).

Complexity: O(n · total) time, O(total) space.

Problem: Players take the first X piles (1 ≤ X ≤ 2M), then M = max(M, X). Return the most stones Alice gets with optimal play.

Solve it on LeetCode ↗

Constraints: 1 ≤ piles.length ≤ 100 · 1 ≤ piles[i] ≤ 10⁴

From brute force to the pattern: The game tree is exponential; memoising (i, M) makes it O(n³).

Spot it: A game with state (start index, M) → memoised game DP. Whatever the mover doesn't get from the remaining suffix, the opponent gets; so the mover maximises suffix[i] − opponent's best.

Why not another pattern? Greedy (take as many as allowed) gives the opponent a bigger M.

Approach:

1. suffix[i] = stones from pile i to the end.
2. best(i, M): if i + 2M ≥ n, take everything: suffix[i].
3. Else suffix[i] − min(best(i + X, max(M, X))) for X = 1..2M.

from functools import lru_cache

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        suffix = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            suffix[i] = suffix[i + 1] + piles[i]  # stones left from i on

        @lru_cache(maxsize=None)
        def best(i, M):  # most stones the player to move gets from piles[i:]
            if i + 2 * M >= n:
                return suffix[i]  # can take everything
            return suffix[i] - min(best(i + X, max(M, X)) for X in range(1, 2 * M + 1))  # leave the opponent the least

        return best(0, 1)

What the code is doing, line by line:

1. Both players share the remaining stones, so the mover gets suffix[i] − what the opponent gets next.
2. Minimising the opponent's best is the same as maximising your own.
3. Taking everything when allowed is always optimal (stones are positive).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Few piles (take all at once).
• Large first pile.
• n = 1.

Complexity: O(n³) time (n² states × O(n) choices), O(n²) space.

Problem: Count all square submatrices that contain only 1s.

Solve it on LeetCode ↗

Constraints: 1 ≤ arr.length ≤ 300 · 1 ≤ arr[0].length ≤ 300 · 0 ≤ arr[i][j] ≤ 1

From brute force to the pattern: Checking every square from every corner is slow; the DP counts them in O(mn).

Spot it: Same DP as Maximal Square: side[r][c] is the largest all-ones square with bottom-right corner (r, c). Such a cell is the corner of exactly side[r][c] squares (sizes 1..side), so add them all up.

Why not another pattern? Checking every square separately is O(m · n · min(m,n)²).

Approach:

1. For each 1 cell (not in the first row/column): side = 1 + min(up, left, up-left).
2. Add side to the total.

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        side = [row[:] for row in matrix]  # largest all-ones square ending at (r, c)
        total = 0
        for r in range(m):
            for c in range(n):
                if side[r][c] and r and c:
                    side[r][c] = 1 + min(side[r - 1][c], side[r][c - 1], side[r - 1][c - 1])
                total += side[r][c]  # squares of size 1..side end here
        return total

What the code is doing, line by line:

1. First row and column cells can only be 1×1 squares, so they keep their value.
2. A corner with largest square s also ends squares of every smaller size.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All zeros → 0.
• All ones.
• One row.

Complexity: O(m · n) time and space.