One-dimensional DP

In many DP problems the state is one number: a position in a list or a string, or an amount. The table is then a single row. The hard part is not the code but saying exactly what each entry means. This lesson shows four common meanings.

One answer per position

For a list of n items, the two most common states are:

• a prefix: the answer for the first i items, a[:i], filled from i = 0 upwards;
• a suffix: the answer for the items from i to the end, a[i:], filled from the end backwards.

Both lead to correct methods. Choose the one that makes the rule shorter. A prefix rule usually looks at the last item; a suffix rule at the first.

Take it or leave it

Choose values from a list so that no two chosen values are side by side, with the largest total. Let best[i] be the largest total using positions 0 to i. The value at position i is either skipped or taken:

• skipped: the best is best[i - 1];
• taken: position i − 1 must be skipped, and the rest is a best choice from positions 0 to i − 2, so best[i - 2] + a[i].

Every choice falls into one of the two cases, and in each case the rest must be a best choice (lesson 1’s argument), so best[i] is the larger of the two. Step through the first version of the figure.

def best_total(a):
    before, best = 0, 0        # best[i - 2], best[i - 1]
    for x in a:
        before, best = best, max(best, before + x)
    return best

Only the last two answers are needed, so two names replace the list: O(n) time, O(1) space. Starting both at 0 stands for the empty prefix, which also makes an empty list return 0.

Fixing where it ends

The largest sum of a stretch (DVCQ-1) is harder to describe with prefixes: the best stretch in a[:i] may be far from position i, so it says nothing about how to extend it. The way out is to fix where the stretch ends. Let end[i] be the largest sum of a stretch that ends exactly at position i. Such a stretch is either the value a[i] alone, or a stretch ending at i − 1 with a[i] added, and the best of those is end[i - 1] + a[i]. The second version of the figure fills it.

def best_stretch(a):
    end = best = a[0]
    for x in a[1:]:
        end = max(x, end + x)      # extend, or start again
        best = max(best, end)
    return best

This is Kadane’s method, O(n). The answer is not end[n − 1] but the largest end[i], because the best stretch can end anywhere.

Lesson 6 uses the same idea: the longest rising subsequence that ends at position i.

Splitting a string

Can a string be cut into pieces that are all words from a given set? Let ok[i] be True if the first i letters can. The last word of such a split ends at i and starts at some j, so ok[i] is True if ok[j] is True and s[j:i] is a word, for some j. The empty prefix can always be split: ok[0] = True.

def can_split(s, words):
    longest = max(map(len, words), default=0)
    ok = [True] + [False] * len(s)
    for i in range(1, len(s) + 1):
        for j in range(max(0, i - longest), i):
            if ok[j] and s[j:i] in words:
                ok[i] = True
                break
    return ok[len(s)]

Only the last longest places can start the last word, so for n letters and words up to L letters long there are O(n · L) checks, each taking O(L) to slice and hash: O(n · L²), where L² means L multiplied by L. A trie of the words (TRIE) checks all the j for one i in a single walk, which removes one factor of L. Pass words as a set, so that in is fast.

Looking further back

Sometimes the rule reads an entry far back, and finding it is part of the work. GRDY-3 ended with bookings that have values, where no greedy rule works. Sort the bookings by end time. Let best[i] be the largest total value from the first i bookings. Booking i is skipped (best[i - 1]), or taken, and then only bookings that end by its start can go with it. Those are a prefix of the sorted list, and binary search finds its length:

from bisect import bisect_right

def most_value(bookings):          # (start, end, value)
    bookings = sorted(bookings, key=lambda b: b[1])
    ends = [b[1] for b in bookings]
    best = [0] * (len(bookings) + 1)
    for i, (s, e, v) in enumerate(bookings, 1):
        p = bisect_right(ends, s, 0, i - 1)  # end <= s
        best[i] = max(best[i - 1], best[p] + v)
    return best[-1]

That is O(n log n): one sort and one binary search per booking. Half-open times are used, as in GRDY-3, so a booking that ends at 5 can be followed by one that starts at 5.

Now try DYNP-P4, Season tickets.