Choosing the state
In Frog 1, Climbing Stairs and Coin Change the states were easy to pick: a stone, a step, an amount of money. The value of each state was a cost or a count. The four problems in this lesson are solved the same way, by choosing states and finding a transition for each, but each one needs more thought about what a state is and what value it holds.
A table of yes and no
The first problem has a string as its input. Its states are the prefixes of the string, and each one's value is a yes or a no.
Given a string s and a list of dictionary words wordDict, return whether s can be split into a sequence of dictionary words. A word may be used more than once.
Constraints
-
s.length -
wordDict.length - Each word has 1 to 20 lowercase letters, and the words are distinct
Sample 1 · Input
s = "leetcode", wordDict = ["leet","code"]
Output
true
Sample 2 · Input
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output
false
Let ok[i] say whether the first characters of s can be split into dictionary words. Look at the last word of such a split. It starts at some position and ends just before position , and the characters in front of it must themselves split into words. So ok[i] is true when some has ok[j] true and the characters from position up to, but not including, position form a dictionary word.
Each gives one candidate, a possible value for the state from one possible last step. The frog combined its candidates with a minimum and Climbing Stairs with a sum, and here they are combined with "at least one". The base case is ok[0], which is true: an empty string needs no words.
That piece of the string is the slice s[j:i]. The listing puts the words in a set, so that testing whether a piece is a word takes one lookup.
def word_break(s, words):
words = set(words)
ok = [True] + [False] * len(s)
for i in range(1, len(s) + 1):
for j in range(i):
if ok[j] and s[j:i] in words:
ok[i] = True
break
return ok[len(s)]
print(word_break("leetcode", ["leet", "code"]))
print(word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]))For "leetcode" the true entries are 0, 4 and 8: "leet" covers positions 0 to 4 and "code" covers 4 to 8. For "catsandog" they are 0, 3, 4 and 7, reached by "cat", by "cats", and by "cat" + "sand" or "cats" + "and". No dictionary word runs from a true entry to the end of the string, so ok[9] stays false.
For a string of characters the table has states, and entry tries up to values of . With 300 characters that is pairs. Each test also copies the piece of the string it looks up, and in the worst case the pieces add up to about characters, which is still fast.
Take or skip the last item
In the problems so far, the last choice was a move: a jump, a climb, a coin or a word. In the next one, the choice is whether to use an item at all.
nums gives the money in each house along a street. Robbing two adjacent houses sets off an alarm, so you may not rob two neighbours. Return the most money you can take.
Constraints
-
nums.length -
nums[i]
Sample 1 · Input
nums = [1,2,3,1]
Output
4
Sample 2 · Input
nums = [2,7,9,3,1]
Output
12
In the second sample the best choice is houses 0, 2 and 4, for . Let best[i] be the most money you can take from the first houses, so best[0] is 0 and the answer is best[n]. The last of those houses is house , and there are two things you can do with it:
- Skip it. Then only the first houses matter, and the most they give is
best[i - 1]. - Rob it. Then its neighbour, house , must be left alone, so the rest of the money comes from the first houses. The total is
best[i - 2] + nums[i - 1].
The entry best[1] has no best[-1] to read, so it is a second base case: the first house alone, nums[0]. For the second sample the table is [0, 2, 7, 11, 11, 12].
The transition reads only the two entries before best[i], so the program keeps those two in variables and no table, the way the Climbing Stairs loop could. prev holds best[i - 2] and cur holds best[i - 1]. Starting both at 0 makes the first house work without a case of its own.
def rob(nums):
prev, cur = 0, 0
for x in nums:
prev, cur = cur, max(cur, prev + x)
return cur
print(rob([1, 2, 3, 1]), rob([2, 7, 9, 3, 1]))The assignment computes both new values from the old pair before it changes either name. After each house of the second sample the pair (prev, cur) is (0, 2), (2, 7), (7, 11), (11, 11) and (11, 12), and the answer is the last cur, 12.
Deeper read: take or skip a job with binary search
Job runs from startTime[i] to endTime[i] and pays profit[i]. Choose jobs whose time ranges do not overlap, with the largest total profit. A job ending at time is compatible with one starting at .
Constraints
-
startTime[i]endTime[i] -
profit[i]
Sample · Input
startTime = [1,2,3,3] endTime = [3,4,5,6] profit = [50,10,40,70]
Output
120
The sample takes the job from 1 to 3 and the job from 3 to 6, for . Each job is taken or skipped, as each house was. A robbed house ruled out one neighbour. A taken job rules out every job that overlaps it, so the "take" branch has to reach further back.
Sort the jobs by end time, and let best[i] be the largest profit from the first jobs in that order. The job after the first is at position , with positions counted from 0, and to compute best[i + 1] we decide whether to take it. Skipping it leaves best[i]. Taking it leaves room for exactly the jobs that end at or before its start time, and because the jobs are sorted by end time, those are the first jobs for some :
Here is the profit of the job at position , and is the number of jobs that end at or before its start. The end times are sorted, so a binary search finds .
def job_scheduling(start_time, end_time, profit):
jobs = sorted(zip(end_time, start_time, profit))
ends = [e for e, _, _ in jobs]
best = [0] * (len(jobs) + 1)
for i, (e, s, p) in enumerate(jobs):
k = bisect_right(ends, s)
best[i + 1] = max(best[i], best[k] + p)
return best[-1]
print(job_scheduling([1, 2, 3, 3], [3, 4, 5, 6], [50, 10, 40, 70]))On the sample, best fills as 0, 50, 50, 90 and 120. best[k] is always ready when it is read: a job ends after it starts, so the jobs that end by its start all come before it in the sorted order.
The kind of binary search matters. bisect_right counts the end times equal to the start, which lets a job ending at 3 sit before a job starting at 3. With bisect_left the sample returns 70.
At the limits there are 50,000 binary searches of about 16 steps each, about steps, plus the sort.
A state for each ending position
Most states so far described a prefix of the input: the stones up to , the first characters, the first houses. For some problems a prefix does not hold enough information to write a transition. The longest increasing subsequence is one of them.
Return the length of the longest strictly increasing subsequence of nums. A subsequence keeps elements in their original order but may skip some.
Constraints
-
nums.length -
nums[i]
Sample 1 · Input
nums = [10,9,2,5,3,7,101,18]
Output
4
Sample 2 · Input
nums = [7,7,7,7,7,7,7]
Output
1
Try the prefix state first: the length of the longest increasing subsequence among the first values. To extend it by the next value, we would need to know whether that value is larger than the subsequence's last element, and the length does not say. Take [1, 5, 3, 4]. After three values the longest increasing subsequence has length 2, but it could be 1, 5 or 1, 3. The value 4 extends the second and not the first, and the answer, 3, depends on the difference.
So the state says where the subsequence ends. Let dp[i] be the length of the longest increasing subsequence whose last element is nums[i]. Now the last-step question has an answer. The element before nums[i] is some earlier, smaller nums[j], and the longest subsequence ending there has length dp[j]:
When no earlier value is smaller, the subsequence is nums[i] alone and dp[i] is 1. The longest subsequence can end anywhere, so the answer is the largest entry of the table, which need not be the last one. For the first sample, [10, 9, 2, 5, 3, 7, 101, 18], the table is [1, 1, 1, 2, 2, 3, 4, 4].
def length_of_lis(nums):
dp = [1] * len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]), length_of_lis([7, 7, 7, 7, 7, 7, 7]))There are states and each one scans every earlier index, so at the limit the comparisons number
nums[i] to the earlier value that set dp[i]. Following the green arcs back from 101 spells out the subsequence 2, 5, 7, 101.The arcs are parent links, like the ones that rebuilt the frog's route in Frog 1. To print a longest subsequence and not only its length, record in parent[i] the first index that gave dp[i] its value, or when nums[i] stands alone. For the sample the parents are [-1, -1, -1, 2, 2, 3, 5, 5]. Start at an index with the largest dp, here index 6, and follow the parents: 6, 5, 3, 2. Read backwards, those indices hold 2, 5, 7 and 101.
Deeper read: a faster LIS with binary search
The table above takes about comparisons. That is fine for 2,500 values, but for 200,000 values it would be about . A different state brings the work down to one binary search per value.
Read the values from left to right and keep a list tails, where tails[k] is the smallest value that can end an increasing subsequence of length built from the values read so far. A smaller last value is always better, because more of the later values can extend it, so the smallest is the only one worth remembering for each length.
tails is always sorted in increasing order. Dropping the last element of a subsequence of length leaves one of length that ends in a smaller value, so the smallest ending for length is below the smallest ending for length . Because the list is sorted, a binary search can find the first entry that is at least the new value , and one of two things happens:
- There is no such entry. Then is larger than every ending, so it extends the longest subsequence so far, and it is appended.
- There is one, at position . Every entry before it is smaller than , so can end a subsequence of length , and is no larger than the ending stored there. It replaces that entry.
On the first sample the list changes like this:
- 10 starts the list. 9 and then 2 each replace its only entry, so the list is
[2]. - 5 is appended and the list is
[2, 5]. 3 replaces the 5 and the list is[2, 3]. - 7 and 101 are appended and the list is
[2, 3, 7, 101]. 18 replaces the 101.
The final list, [2, 3, 7, 18], has 4 entries, and 4 is the answer. The list itself need not be a subsequence of the input. For [3, 4, 1] it ends as [1, 4], although 1 comes after 4. Only its length means something.
def length_of_lis_fast(nums):
tails = []
for x in nums:
k = bisect_left(tails, x)
if k == len(tails):
tails.append(x)
else:
tails[k] = x
return len(tails)
print(length_of_lis_fast([10, 9, 2, 5, 3, 7, 101, 18]))Each value costs one binary search over at most entries, so 200,000 values take about steps.
Two values for each ending position
The state of the next problem also fixes an ending position, and one number per state is not enough for it.
Return the largest product of a non-empty contiguous subarray of nums. The answer fits in a 32-bit integer.
Constraints
-
nums.length -
nums[i]
Sample 1 · Input
nums = [2,3,-2,4]
Output
6
Sample 2 · Input
nums = [-2,0,-1]
Output
0
Kadane's algorithm, which finds the largest sum of a contiguous subarray, also fixes an ending position, and it needs only one number per state: the largest sum of a subarray that ends at that index. That subarray is either nums[i] alone or the best subarray ending at extended by nums[i]. The widget runs it on [-2, 3, -4]. Its "best ending here" row is the state, and "best" is the largest value the state has taken so far.
For sums, one value per index is enough, and the largest sum here is 3. Now try the same state for products: the largest product of a subarray ending at each index. At the 3 it is 3, from [3]. At the it is 24, from [-2, 3, -4]. That subarray extends [-2, 3], whose product, , is the smallest product of a subarray ending at the 3. Multiplying by a negative number turns the smallest product into the largest, so the largest product at one index cannot be computed from the largest product at the index before.
Keep the largest and the smallest product
So each state keeps two values: hi, the largest product of a subarray ending at the current index, and lo, the smallest. A subarray ending at the next value is alone, or added to the end of a subarray ending at the index before. Multiplying by keeps the order of the earlier products when is positive and reverses it when is negative, so among the longer subarrays, the largest and the smallest products come from the ones with products hi and lo. The new pair, marked with a prime in the formula, is the largest and the smallest of those three candidates:
def max_product(nums):
hi = lo = best = nums[0]
for x in nums[1:]:
hi, lo = max(x, hi * x, lo * x), min(x, hi * x, lo * x)
best = max(best, hi)
return best
print(max_product([2, 3, -2, 4]), max_product([-2, 0, -1]), max_product([-2, 3, -4]))On [-2, 3, -4] the pair (hi, lo) starts at the first value, and each later value takes the largest and the smallest of its three candidates:
The answer is the largest hi seen along the way, 24.
Time and space of these tables
- Word Break
lookups - State tries every split point , and each lookup copies up to characters.
- House Robber
time, space - states with two candidates each, kept in two variables.
- Job Scheduling
time - A sort, then one binary search per job.
- Longest increasing subsequence
time, or - State scans every earlier index. The
tailslist needs one binary search per value. - Maximum product
time, space - Two values per index, each from three candidates.
Common mistakes
Returning the last entry of the increasing-subsequence table.
- Where it breaks
- For
[2, 3, 1]the table is[1, 2, 1]. Its last entry is 1, but the answer is 2, from the subsequence 2, 3, which ends at index 1. - The fix
- Return the largest entry. A state that fixes the last element answers the question for one ending, and the best ending can be anywhere.
Keeping only the largest product for each ending position.
- Where it breaks
- On
[-2, 3, -4]a version that keeps only the largest product computes , 3 and for the three ending positions and returns3. The largest product ending at the last index is really 24, and finding it needs the smallest product ending at the 3. - The fix
- Keep the smallest product as well, and take the largest and the smallest of the three candidates at every index.
Searching for the first entry greater than in the binary-search LIS.
- Where it breaks
- The sample
[7, 7, 7, 7, 7, 7, 7]returns7: each equal value lands after its twin and lengthens the list. The answer is1. - The fix
- Search for the first entry that is at least (
bisect_leftin Python,lower_boundin C++) when the subsequence must be strictly increasing. The other search (bisect_right,upper_bound) gives the longest non-decreasing subsequence.
Recall Suppose the frog in Frog 1 may also make one jump of three stones, once in the whole trip. Why is one cheapest cost per stone no longer enough?
Two arrivals at the same stone are no longer interchangeable. One may still have the long jump in hand while the other has spent it, and the cheaper arrival can be the one that spent it, which leaves it fewer options for the rest of the trip. Throwing away the more expensive arrival could throw away the best route.
The state needs the missing fact. Keep two values per stone, the cheapest cost of reaching it with the long jump unused and the cheapest cost with it used, the way Maximum Product kept two values per index.
One more problem and two related lessons
One more problem reuses the increasing-subsequence table, and it is left for you to try. String DP and stock DP choose their states in ways that get lessons of their own, though their problems also appear in this chapter's problem list. The next lesson in the chapter, DP on DAGs, is about the order in which a table can be filled.
Judge problems
- Minimum Number of Removals to Make Mountain Array(opens the judge in a new tab) ↗
Deleting the fewest elements means keeping the longest subsequence that rises to a peak and then falls. For a peak at index , the rise is an increasing subsequence ending at , and the fall is the same table filled from the right. The peak needs at least one element on each side.
Related chapters
- LCS and edit distance →
The state is a pair of prefixes, one from each string: longest common subsequence, edit distance and counting subsequences.
- Stock trading DP →
The state is what you hold on each day: buying and selling with a cooldown, a fee or a limit on trades.