Subsequence patterns and DP habits in Python

Why it matters

By now you have seen the DP recipe on a line of houses, a grid of cells, and a pair of strings. Real interview problems rarely announce which pattern they are. The statement describes a story, and you must recognise the shape underneath. This lesson adds two more patterns, the subset sum and the range of a single string, and then gives you a checklist you can follow on any new problem. The checklist matters as much as the two patterns, because most candidates who fail a DP question do not lack a formula. They start writing code before they have decided what the state means.

The lesson has three parts. First comes subset sum, which asks whether some of the numbers add up to a target. Second comes the longest palindromic subsequence, which fills a table by ranges rather than by prefixes. Third comes the checklist and a worked example of applying it to a problem that is new to you. At the end you will have a clear method for a DP problem that does not match any pattern in this module exactly.

You should have finished the earlier lessons. You should know the recipe, the difference between a subsequence and a substring, and why some loops must run in reverse. Every program is a plain Python file. The programs marked python run print their output without reading input. Where a program reads input, the lesson tells you what to type when it asks.

Subset sum: can we hit the target?

Here is a story. A shop has a set of coins or bills of different values, and each one can be spent at most once. A customer wants to pay an exact amount, such as 9 units, using some of the coins. Is it possible? The answer is yes or no. You do not need to name the coins, only to decide whether the target can be made. This is the subset sum problem.

Take the numbers 3, 34, 4, 12, 5, 2 and the target 9. The answer is yes, because 4 + 5 = 9. For the target 30 the answer is no. You might try a few combinations by hand. With six numbers there are 64 subsets, which is manageable for a person, but the count doubles with every extra number. A DP table answers the question in time proportional to the number of numbers times the target, which is far better when the target is moderate.

Subset sum is a yes-or-no cousin of the 0/1 knapsack from earlier in this module. The knapsack asked for the best value. Subset sum asks only whether a value is reachable. Because the answer is true or false, the table holds booleans instead of numbers, which makes it smaller and easier to read. In Python a boolean is True or False.

The state and the recurrence

State: dp[s] is True if some subset of the numbers seen so far adds up exactly to s. The state is one number, the sum, so the table is one row. Each number in the list is a new chance to reach each sum.

Base case: dp[0] = True, because the empty subset adds up to 0. Nothing needs to be chosen to reach zero. Every other cell starts as False, because before we see any numbers we cannot reach any positive sum.

Recurrence: when we process a number x, a sum s becomes reachable in two ways. Either it was already reachable without x, or it is reachable with x by taking the sum s - x that was reachable before x was seen. So:

dp[s] = dp[s] or dp[s - x]

This is only checked for s at least x, because a sum smaller than x cannot include x.

The loop must go in reverse

Here is the detail that repeats from the knapsack. The formula reads dp[s - x], and that cell must hold the value from before this number was processed. If the loop for s ran upward, from x to the target, then dp[s - x] might already have been set to True in this same pass by the number x itself. The number would be used twice, once to reach s - x and once to add x again. Running the loop downward, from the target to x, guarantees that dp[s - x] is still the old value. Each number is used at most once.

A trace for the numbers 2, 3, 7 and target 10

Here is the table as each number is processed. Each row shows which sums are reachable after that number. Sums from 0 to 10 are listed in the middle column.

Look at the row for 7. The new sums come from adding 7 to an old reachable sum that is small enough: 0 + 7 = 7, 2 + 7 = 9, 3 + 7 = 10. The sum 5 was already reachable, and 5 + 7 = 12 is above the target, so it is ignored. The sum 10 is reachable through 3 + 7, so the answer for target 10 is True. The subset is 3 and 7.

The next program prints the whole boolean list, so you can check each cell against the trace. It does not read input.

The output is:

[0, 2, 3, 5, 7, 9, 10]
can make 10: True

The list comprehension [s for s in range(len(dp)) if dp[s]] keeps only the positions where the cell is True. Python prints the list with brackets and commas, so you do not get the trailing space that a loop with print(s, end=" ") would leave.

The program that reads input

The next program reads the number of values, the values, and the target from the input. It uses the same method, now on your numbers. Type these lines when it asks for input:

6
3 34 4 12 5 2
9

def subset_sum(nums, target):
    dp = [False] * (target + 1)
    dp[0] = True
    for x in nums:
        for s in range(target, x - 1, -1):
            dp[s] = dp[s] or dp[s - x]
    return dp[target]
 
 
n = int(input())
nums = [int(x) for x in input().split()]
target = int(input())
print("yes" if subset_sum(nums, target) else "no")

The output is:

yes

Change the last line of the input from 9 to 30 and run the program again. The output is no. The numbers below 34 add up to 26 in total, and 34 is too big to use for a target of 30, so no subset reaches 30.

The range range(target, x - 1, -1) counts down from the target to x, and it stops before x - 1. That is the same downward loop as in the knapsack. Read the line dp[s] = dp[s] or dp[s - x] carefully. It always writes the cell. That is harmless here, because a cell that was True stays True, and the write only changes a False to True when dp[s - x] is True.

The partition question

A famous use of subset sum asks whether an array can be split into two groups with equal sums. The answer is no if the total is odd, because two equal integer sums must add up to an even number. If the total is even, let the target be half the total. The array can be split evenly exactly when some subset sums to that target, which is subset sum again.

Take 1, 5, 11, 5. The total is 22, the half is 11, and 11 alone is a subset with sum 11. The other group is 1, 5, 5, which also sums to 11. So the answer is yes. The next program applies this rule to input. Type these lines when it asks for input:

4
1 5 11 5

def can_split(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    half = total // 2
    dp = [False] * (half + 1)
    dp[0] = True
    for x in nums:
        for s in range(half, x - 1, -1):
            dp[s] = dp[s] or dp[s - x]
    return dp[half]
 
 
n = int(input())
nums = [int(x) for x in input().split()]
print("YES" if can_split(nums) else "NO")

The output is:

YES

Type 3 then 1 2 4 instead, and the output is NO, because the total is 7, which is odd. The // operator is integer division, which gives a whole number, so total // 2 is exact when the total is even. The program never needs to know which numbers go in each group. It only decides whether a split is possible. If the problem asked for the groups themselves, you would need to store the choices, which the knapsack recovery in the third lesson showed you how to do.

Python integers do not overflow, so the total can be as large as you need. For counting versions of this problem, the number of ways can grow fast, but Python keeps every digit. Some other languages would need a bigger type, as the first lesson explained for Java.

The longest palindromic subsequence: a table over ranges

The second pattern is different in an important way. The state is a range of one string, not a prefix. A palindrome reads the same forwards and backwards, like level or abba. We want the longest subsequence of a string that is a palindrome. As before, a subsequence may skip letters.

Take the string bbbab. The longest palindromic subsequence is bbbb, which takes the three bs and the final b, skipping the a. Its length is 4. For cbbd it is bb, length 2. Notice the answer does not have to be contiguous. In bbbab the bs are not all together, and the answer still counts them.

The state: a range of indexes

State: dp[i][j] is the length of the longest palindromic subsequence inside the part of the string from index i to index j, including both ends. Two indexes describe a range, so the table is two-dimensional. Notice that this is different from the earlier string tables, where the indexes were prefix lengths. Here the table covers every range, and the answer is the range from the first letter to the last.

Base case: a single letter is a palindrome of length 1. So dp[i][i] = 1 for every i. A range where i is greater than j is empty, and an empty range has length 0.

The recurrence

Look at the two ends of the range, s[i] and s[j].

• The ends match. Both can be used around the best answer for the range inside them. So dp[i][j] = dp[i + 1][j - 1] + 2. The inner range is from i + 1 to j - 1, and the two matching ends add 2 to its answer.
• The ends differ. They cannot both be used at the same time. Drop one end, and keep the better of the two results: dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]).

The inner range can be empty when j = i + 1. Then dp[i + 1][j - 1] reads dp[i + 1][i], which is an empty range, so it is 0. Two matching neighbouring letters, such as aa, get 0 + 2 = 2, which is correct.

The order of filling

This is the detail that differs from the earlier tables. A cell dp[i][j] reads cells with a smaller range: dp[i + 1][j], dp[i][j - 1] and dp[i + 1][j - 1]. The ranges that are shorter must be filled first. The simplest safe order is to let i run from the last index down to 0, and for each i, let j run from i + 1 up to the last index. Then dp[i + 1][...] is complete before row i needs it, because it belongs to the row for the larger i, which was filled in an earlier step of the outer loop.

Compare this with the grid. There the order was top to bottom, because each cell read the row above. Here the order is bottom to top, because each cell reads the row below. Getting the direction wrong is the most common bug in this pattern, and it reads an empty or unfilled cell without any error message.

A trace for bbbab

Here is the answer table for the string b b b a b, with indexes 0 to 4. Only the upper half is used, so the lower half is left blank. The Python program below prints the same numbers, with 0 in the blank cells.

Check the top-right cell dp[0][4]. The ends are b and b, which match. The inner range from index 1 to 3 is bba, whose answer is dp[1][3] = 2 (the bb). So dp[0][4] = 2 + 2 = 4. Check dp[0][3]: the range is bbba. The ends are b and a, which differ, so take the larger of dp[1][3] = 2 and dp[0][2] = 3. That gives 3, which is correct, because bbb is a palindrome of length 3. The answer is the top-right cell, 4.

The code for the palindrome table

The next program reads a single word from the input. It fills the range table with the order described above. Type this when it asks for input:

bbbab

def longest_pal_subseq(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        dp[i][i] = 1
        for j in range(i + 1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]
 
 
s = input().strip()
print("longest palindromic subsequence:", longest_pal_subseq(s))

The output is:

longest palindromic subsequence: 4

Try cbbd next. The output is 2. The method strip() removes spaces and the newline from the ends of the text, so a stray space at the end of the input does not change the answer.

Look closely at the case j = i + 1. The code reads dp[i + 1][j - 1], which is dp[i + 1][i]. That cell is in the lower half of the table, which the program never writes, so it is still 0. That zero is exactly what an empty range needs. The code is correct because of this unwritten zero, and a future change that writes the lower half would break it. Mention this in a code review, because it is the kind of detail that interviewers ask about.

Palindromic subsequence and the reversed string

There is a useful trick. The longest palindromic subsequence of s equals the longest common subsequence of s and its reverse. A palindrome reads the same forwards and backwards, so a subsequence that is a palindrome is also a common subsequence of s and s[::-1]. The slice s[::-1] makes a reversed copy of the string. You can use the LCS table from the last lesson, which is simpler to write if you already know it. The next program checks the trick on four words, using both methods. It does not read input.

The output is:

agbcba: palindrome table = 5, LCS with reverse = 5
abca: palindrome table = 3, LCS with reverse = 3
level: palindrome table = 5, LCS with reverse = 5
abc: palindrome table = 1, LCS with reverse = 1

The two methods always agree, which is why the trick is reliable. Use the table for ranges when the problem asks about a palindrome directly. Use the reverse trick when you already have an LCS routine and want to save time writing code. In an interview, state the trick first, then write the range version, which shows you understand the structure of the problem.

What happens inside: why range tables need a careful order

The memory for a range table is a two-dimensional list of n * n integers. Half of it is never used, because the code only writes cells with i <= j. You could store only the upper half, which halves the memory, but the code becomes harder to read. Interviewers expect you to mention this and to know that it is possible.

The order of the outer loop is the important part for correctness. When the outer loop reaches row i, every row below it, from i + 1 to n - 1, has already been filled completely, because those rows were visited in earlier outer iterations. The cell dp[i + 1][j - 1] belongs to one of those finished rows. So reading it is safe. If you ran the outer loop upward, row i + 1 would still be empty when row i read it, and the table would be wrong without any error message.

The inner loop runs j upward within the row, and that order matters too. A cell in row i reads dp[i][j - 1], which is one column to the left in the same row. That cell was filled earlier in this same inner loop, because j - 1 is visited before j. So the inner loop must go upward.

The next program shows the wrong order. It fills the rows from the top, so each row reads a row that is still empty. The answer for bbbab is 2, not 4, and it does not stop with an error.

The output is 2 2. The second answer is right only by luck, because aa needs just one matching pair.

Recognising the pattern: the checklist

Here is the most useful part of the lesson. When you meet a DP problem you have not seen, follow this checklist. Each step gives you something to write down, so you do not start typing code too early.

1. Is DP likely? Does the problem ask for a count, a minimum or maximum, or a yes-or-no answer, and does a brute force try choices in a way that repeats work? If the brute force would try every subset, every ordering or every path, DP is a good candidate.
2. Write the brute-force recursion first. Write it in words or as a short function. Note which values change from one call to the next. Those values are the parameters of the state.
3. Name the state. Write one sentence that says what dp[...] means, with each parameter named. If you cannot write this sentence, you do not yet understand the problem. Go back to step 2.
4. Count the states and estimate the time. Multiply the number of possible values for each parameter. If the count is n * target, the time will be about that many steps times the work per step.
5. Add memoization, check the examples, then convert to a table. Memoization is the easiest to get right, because it follows the brute force exactly. Check the examples with it. Only then convert to a table, and remember that the table must fill in an order where every read is already written.
6. Shrink the space if you can. Look at which earlier cells each new cell reads. If only the previous row or two previous cells matter, keep fewer rows or variables.

The table below groups the problems in this module by their shape. When you meet a new problem, compare its state with these shapes first. A close match tells you the recurrence almost at once.

Applying the checklist to a new problem

Suppose you meet this problem, which you have not seen before: Given a list of positive integers and a target, count the number of subsets whose sum is exactly the target. Use the checklist.

Step 1: the problem asks for a count, and a brute force would try every subset. DP is likely. Step 2: the brute force is "for each number, either take it or leave it, and recurse". The values that change are the index in the list and the remaining target. Step 3: the state is ways[i][s], the number of subsets of the first i numbers that sum to s. Step 4: the number of states is n * target, so the time is about that many operations. Step 5: the recurrence is ways[i][s] = ways[i - 1][s] + ways[i - 1][s - x] when s >= x. Base case: ways[0][0] = 1, because the empty subset is the one way to reach zero. Step 6: the rows depend only on the row above, so a single list ways[s] works, with the same downward loop as subset sum.

Notice what changed from subset sum. The boolean became a count, or became +, and the base case became 1 instead of True. The loop direction stayed the same. Once you see that a counting problem is the same shape as a yes-or-no problem with + in place of or, you can solve both quickly. Check the recurrence on the example 1, 2, 3 with target 3: the subsets are {3} and {1, 2}, so the answer is 2. The program below checks it.

The output is 2.

Common mistakes

Mistake 1: starting to code before naming the state. Most wrong solutions have a sound recurrence applied to the wrong state. Write the sentence about dp[...] first. If the sentence is vague, the table will be wrong.

Mistake 2: filling a range table in the wrong order. If the outer loop runs upward, dp[i + 1][...] is still empty when row i reads it. The result is a wrong answer with no error, as the wrong-order program shows. Print a small table to check: the bottom rows must be filled before the top ones.

Mistake 3: an upward loop in subset sum. The number is used twice. For {2, 3, 7} and a target of 4, an upward loop sets dp[4] to True by using 2 twice, which is wrong. The program below shows it. The correct answer for target 4 is False, because no subset of 2, 3, 7 adds to 4.

The output is upward: True and downward: False. The fix is the same as in knapsack: the loop goes from the target down to the number.

Mistake 4: relying on an unwritten zero in the palindrome table. For adjacent matching letters, the code reads dp[i + 1][j - 1], an empty range. It works only because a new list of integers starts with 0, and the lower half is never written. If you change the table so that cells are filled in another way, set the empty range to 0 on purpose. Otherwise the code can read a value you did not intend, and the answer is wrong without any error.

Mistake 5: forgetting the empty-input base case. An empty list in subset sum means dp[0] is True and nothing else is reachable, and the code handles that. An empty string in the palindrome table gives n = 0, so the table has no rows, and the final read dp[0][n - 1] asks for row 0 of an empty table. Check if n == 0: return 0 at the top of the function. Without the check, the program stops with this error when the input is empty:

    return dp[0][n - 1]
           ~~^^^
IndexError: list index out of range

The message means the list has no item at position 0, because the table is empty.

Mistake 6: using a fixed-size type for a count that can be large. A counting version of subset sum can give huge numbers, because the number of subsets doubles with every item. Python integers grow as needed, so this is not a problem in this language. When the statement gives a modulus, such as "give the answer modulo 1,000,000,007", take the remainder with % after each addition, so the numbers stay small.

Mistake 7: input that does not match the program. The subset sum program reads a count, then a line of values, then a target. If the count and the values are on one line, int(input()) fails with this message:

ValueError: invalid literal for int() with base 10: '6 3 34 4 12 5 2'

Check the order of the lines against what the program asks for, one line at a time.

Debugging a DP program that has the right recurrence

When the recurrence looks right but the answer is wrong, the cause is almost always the fill order or the base cases. Check those in this order. First, print the table for the smallest input you can handle, such as one number or a one-letter string. Second, check that the base cases match the printed values. Third, look at the first cell you computed by hand that differs from the printed table, and find which earlier cells it read. If those cells were not yet written, the fill order is wrong.

For subset sum, a quick test is [2] with target 2, which must be True. If the program prints False, the loop is probably downward but stops too early, or the base case dp[0] = True is missing. For the palindrome table, a quick test is the string aa, which must give 2. If it gives 1, the match case is missing.

Edge cases you should test

• Subset sum with target 0: the answer is True, because the empty subset makes 0.
• Subset sum with an empty list: the answer is True for target 0 and False for any positive target.
• Subset sum where a number is bigger than the target: that number is never used, and the loop does not run for it.
• Palindrome with one letter: 1. With two equal letters: 2. With two different letters: 1.
• Palindrome of a string that is already a palindrome: its length.
• Palindrome with no repeated letters, such as abc: 1.

Interview questions you should expect

"What is the time and space complexity of subset sum?" Time is O(n * target), where n is the number of values. Space is O(target) with the one-row version. Say that this is pseudo-polynomial, because the time depends on the size of the target number, not only on the count of numbers.

"How would you find the subset itself?" Keep the table for each number, as in the knapsack recovery, and walk back from the target. This needs O(n * target) memory. A cheaper method stores one parent choice per reachable sum, which uses O(target) memory with a little more code.

"What is the complexity of the palindrome table?" Time and space are both O(n^2). You can reduce the space to O(n) in some versions, but the table version is the one to explain first.

"How would you explain the palindrome recurrence in one sentence?" If the two ends of the range match, they wrap the best answer for the inside, adding 2. If they do not match, one of them must be dropped, so take the better result after dropping each one.

"Why does the palindrome table fill from the end of the string?" Because each cell reads cells for smaller ranges that lie below it in the table, and those must be filled before it.

Practice

Try these before reading the solutions. Work each one with pencil and paper first, then check with the programs.

Exercise 1 (easy). Does [2, 3, 7] contain a subset that sums to 10? Name the subset.

Show the answer

Yes. 3 + 7 = 10. The subset is {3, 7}.

Exercise 2 (easy). Does [4, 4, 4] contain a subset that sums to 8? To 5?

Show the answer

Yes for 8, because 4 + 4 = 8 uses two of the three values. No for 5, because every subset sum is a multiple of 4, so 5 can never be reached.

Exercise 3 (easy). Write the first three cells of the palindrome table for the string ab, and give the answer.

Show the answer

dp[0][0] = 1 for the letter a, dp[1][1] = 1 for the letter b, and dp[0][1] = max(dp[1][1], dp[0][0]) = 1 because the two letters differ. The answer is 1.

Exercise 4 (medium). Fill the palindrome table for aba and give the answer.

Show the answer

The diagonal is 1, 1, 1. For dp[0][1] (letters a and b, differing), max(dp[1][1], dp[0][0]) = 1. For dp[1][2] (letters b and a, differing), max(dp[2][2], dp[1][1]) = 1. For dp[0][2] (letters a and a, matching), dp[1][1] + 2 = 1 + 2 = 3. The answer is 3, which is the whole string.

Exercise 5 (medium). Why does subset sum use s >= x in the loop range, and what would happen without it?

Show the answer

A sum smaller than x cannot include x, so the cell does not need an update, and s - x would be a negative index. In Python a negative index does not raise an error. It reads a cell from the end of the list, so the answer can be wrong with no message.

Exercise 6 (medium). Modify subset sum to count the number of subsets that reach the target instead of only testing whether one exists. Give the recurrence and base case.

Show the answer

Use a list ways with ways[0] = 1. For each number x, loop s from the target down to x and set ways[s] += ways[s - x]. The recurrence is the same shape as the boolean version, with + in place of or. For [1, 2, 3] and target 3 the answer is 2, because {3} and {1, 2} both work. The program in the lesson prints this.

Exercise 7 (medium). Explain in two sentences why the palindrome table must fill row i after the row below it.

Show the answer

Row i reads dp[i + 1][j] and dp[i + 1][j - 1], which belong to the row below. Those cells describe smaller ranges, and they must already hold their final values, so the outer loop goes from the last index down to 0.

Exercise 8 (hard). For abca, find the longest palindromic subsequence and the LCS with its reverse acba. Then explain in one sentence why a palindrome is always a common subsequence of s and its reverse.

Show the answer

The longest palindromic subsequence of abca is aca (length 3). The LCS of abca and acba is also 3, for example aca again. A palindrome equals its own reverse. So it is a subsequence of s, and its reverse, which is the same string, is a subsequence of reverse(s). That makes it a common subsequence of both.

Exercise 9 (hard). Use the checklist to design a DP for this problem: given a list of positive integers, find the length of the longest subsequence in which each number is at least twice the one before it. Name the state, the recurrence and the answer.

Show the answer

State: dp[i] is the length of the longest run that ends at index i where each value is at least twice the previous one. Recurrence: dp[i] = 1 + max(dp[j]) over earlier indexes j with nums[i] >= 2 * nums[j], or 1 if none exists. Base: each cell starts at 1. Answer: the maximum over all dp[i], not dp[n - 1], for the same reason as LIS. The time is O(n^2). The shape matches LIS, with the comparison changed from < to a doubling test.

Summary of this module

• Dynamic programming stores answers to subproblems so each one is computed once.
• Memoization is top-down with a cache, and tabulation is bottom-up with a table.
• Linear tables cover stairs, house robber, coin change and LIS.
• Capacity tables cover knapsack and subset sum, and the 0/1 loop runs downward.
• Grid and two-string tables read the cell above and to the left, and fill row by row.
• Range tables, such as the palindrome, read smaller ranges and fill from the end of the string.
• Follow the checklist: name the state in one sentence before you write any code.

What you now know

• Subset sum is a yes-or-no DP over sums, and it uses a downward loop so each number is used once.
• The longest palindromic subsequence uses a table over ranges, and it fills from the end of the string.
• The longest palindromic subsequence of s has the same length as the LCS of s and its reverse, as the reversed-string trick shows.
• The checklist turns an unfamiliar problem into six small steps, starting with the state.
• Most DP bugs are in the fill order or the base cases, so print a small table when an answer is wrong.