More DP patterns and how to spot them

Longest increasing subsequence (LIS)

Given a list of numbers, find the length of the longest subsequence (gaps allowed, order kept) whose numbers strictly increase. For [10, 9, 2, 5, 3, 7, 101, 18] one answer is [2, 3, 7, 18], length 4.

The O(n²) DP: dp[i] = the length of the longest increasing subsequence that ENDS at index i. It is 1 (just nums[i]) or 1 + dp[j] for any earlier j with nums[j] < nums[i]. The answer is max(dp). Two nested loops give O(n²) time and O(n) space, fine for n up to a few thousand.

The O(n log n) idea keeps a list called tails, where tails[k] is the SMALLEST possible last number of an increasing subsequence of length k + 1. A smaller tail is always better, because more numbers can extend it later. tails stays sorted, so for each x use binary search (bisect_left) to find the first tail ≥ x. If there is none, x extends the longest subsequence: append it. Otherwise replace that tail with x. The answer is len(tails).

from bisect import bisect_left

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

print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))   # Output: 4
# tails after each number: [10] [9] [2] [2, 5] [2, 3] [2, 3, 7] [2, 3, 7, 101] [2, 3, 7, 18]

Maximum product subarray

Find the largest product of a run of neighbouring numbers. Kadane's idea from Module 2 needs a twist: a negative number turns the smallest (most negative) product into the largest. So keep two values for the run ending here: hi (largest product) and lo (smallest product). For each x, the candidates are x, hi × x and lo × x; the new hi is their max and the new lo is their min. A zero resets both to 0, and the next number starts fresh. O(n) time, O(1) space. For [2, 3, −2, 4] the answer is 6; for [−2, 3, −4] it is 24.

Palindromic substrings

Every palindrome has a centre: one character (odd length, like "aba") or the gap between two characters (even length, like "abba"). A string of length n has 2n − 1 centres. From each centre, expand outwards while the two ends match. Each expansion step finds one more palindrome, so counting all palindromic substrings and finding the longest one both take O(n²) time and O(1) extra space.

def count_palindromes(s):
    count = 0
    for centre in range(2 * len(s) - 1):
        left = centre // 2
        right = left + centre % 2
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
    return count

print(count_palindromes("aaa"))   # Output: 6  (a, a, a, aa, aa, aaa)

The DP version uses a table pal[i][j] = True if s[i..j] is a palindrome: s[i] == s[j] and (j − i < 2 or pal[i + 1][j − 1]). Fill it by increasing length. It is also O(n²) time, but needs O(n²) space, so expanding around centres is usually preferred in interviews.

Interval DP and bitmask DP in brief

Interval DP: the state is a range [i, j] of the input, and the answer for a range is built by trying every split point k between i and j. Examples are matrix-chain multiplication and "burst balloons". Fill the table by increasing range length so smaller ranges are ready first. There are O(n²) ranges with O(n) splits each, so O(n³) time.

Bitmask DP: the state includes a SET of items already used, stored as the bits of an integer (Module 10). The classic is the travelling salesman problem on up to about 20 cities: dp[mask][last] = the cheapest way to visit exactly the cities in mask, ending at last. That is O(2ⁿ × n²) time, so it only fits when n is small, which the constraints will tell you.

How to recognise a DP problem

• The question asks for a COUNT ("how many ways"), a best value ("minimum cost", "maximum profit", "longest"), or a yes/no ("can we reach", "is it possible").
• At each step you make a choice (take or skip, which coin, which move), and later choices depend on earlier ones.
• A brute-force recursion would call itself with the same arguments many times.
• The input is a sequence, a string, a grid, or an amount, and the answer for a prefix or a smaller amount helps with the whole.
• Greedy ideas fail on a small counter-example you can find in a minute.

A debugging checklist

1. Write the state in one sentence. Does every cell of your table match that sentence?
2. Check the base cases by hand for the smallest inputs (empty, one item, amount 0).
3. Print the table for a tiny example and compare it with a table you fill on paper.
4. Check the filling order: is every cell you read already final?
5. Check the loop direction (0/1 versus unbounded) and the loop order (combinations versus orderings).
6. Check the answer cell: dp[n], dp[n][m], max(dp), or something else?

Common mistakes

• Using bisect_right for a STRICTLY increasing LIS, which lets equal numbers extend the sequence. Fix: bisect_left for strict, bisect_right for non-decreasing.
• Tracking only the maximum in max product. Fix: track the minimum too, and compute the new hi and lo from the OLD values at the same time.
• Expanding only odd-length centres and missing "abba". Fix: try both centres (i, i) and (i, i + 1).
• Answering with dp[n − 1] in LIS when the best subsequence ends earlier. Fix: in the O(n²) version the answer is max(dp).