How to recognise a DP task in Java

Problem

Which requests should the van take?

You have one rental van. For tomorrow there are six transport requests, each with a start, an end and a price. The van can only be in one place, so two requests that overlap cannot both be taken. Which ones do you accept to earn the most?

The first thing that comes to mind is a greedy rule: the most expensive request first, then the next one that does not get in the way. Or: the one that ends earliest, so more time is left:

static List<Job> greedy(Job[] jobs, Comparator<Job> rule) {
    Job[] queue = jobs.clone();
    Arrays.sort(queue, rule);
    List<Job> taken = new ArrayList<>();
    for (Job job : queue) {
        boolean free = true;
        for (Job t : taken) {
            if (job.start() < t.end() && t.start() < job.end()) free = false;
        }
        if (free) taken.add(job);
    }
    return taken;
}

static void show(String rule, List<Job> taken) {
    int sum = taken.stream().mapToInt(Job::pay).sum();
    List<String> names = taken.stream().map(Job::name).toList();
    System.out.println(rule + ": " + String.join(", ", names) + " = " + "€" + sum);
}

show("Most expensive first", greedy(jobs, Comparator.comparingInt(Job::pay).reversed()));
show("Earliest end first", greedy(jobs, Comparator.comparingInt(Job::end)));

Most expensive first: airport, sofa = €180
Earliest end first: market, office, repair = €170

Both rules leave money on the table: there is a schedule worth more. Trying all 2⁶ = 64 subsets works here, but with 60 requests there are over a billion billion. The task is of the same kind as the knapsack and diff. How do you recognise that yourself, and how do you build the solution?

The idea

The signs

A task is for dynamic programming when it has three things:

The question is about the best or about the count. "Most", "least", "how many ways", "is it possible at all". If it only asks "find the element" or "sort", there is nothing to choose.
Optimal substructure. The best solution of the whole is built from the best solutions of smaller parts. For the van: if the last request is in the best schedule, the rest is the best schedule of the requests that end before it.
Overlapping subproblems. The same smaller parts are asked many times, as with the naive Fibonacci. For the van, "repair" and "airport" both start at 15:00 and ask the same thing: the most from the requests that end by 15:00.

Once all three are there, the answer to every small part is computed once and written down.

The idea

The five-step recipe

State. What one cell is: "best[i] is the most money from the first i requests, sorted by end". A good state describes the small task with one or two numbers.
Transition. How the cell is computed from smaller ones. For request i there are two choices: skip it (best[i − 1]) or take it (its price + best[p], where p is how many requests end by its start). best[i] is the bigger one.
Base. The cells that depend on nothing: best[0] = 0, no requests, no money.
Order. In what order to fill, so that what you need is already done: left to right, because i only uses i − 1 and p < i.
Answer. Which cell is the answer: best[n]. If you also want which requests, you walk back along the choices, like the way back in diff.

Sorting by end is part of the state: that way the requests compatible with the i-th one are exactly the first p, and "the best of them" is one cell.

More precisely, if you are curious

The same recipe works top-down too: a function best(i) that calls best(i − 1) and best(p) and remembers the result (see memoization). The bottom-up table and the recursion with memory compute the same cells. The recursion is closer to the words of the transition, the table has no deep stack.

In Java memoization is a Map<Integer, Integer> or an array with -1 for "not computed yet". Deep recursion can throw StackOverflowError, so for long sequences the table is safer.

p can be found with binary search on the ends, because they are sorted: then the whole is O(n log n). The loop in the lesson is O(n) per request, O(n²) in total, and for six requests it is plenty.

See it

The recipe in code

static int bestPay(Job[] jobs) {
    Arrays.sort(jobs, Comparator.comparingInt(Job::end));
    int n = jobs.length;
    int[] best = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        Job job = jobs[i - 1];
        int p = 0;
        while (jobs[p].end() <= job.start()) p++;
        int skip = best[i - 1];
        int take = job.pay() + best[p];
        best[i] = Math.max(skip, take);
    }
    return best[n];
}

Arrays.sort sorts the array in place, and Comparator.comparingInt(Job::end) says by what. The loop for p stops at the i-th request itself at the latest, because it ends after it starts.

Job[] jobs = {
    new Job("sofa", 9, 12, 80),
    new Job("airport", 15, 20, 100),
    new Job("market", 8, 10, 60),
    new Job("depot", 12, 17, 30),
    new Job("office", 11, 13, 60),
    new Job("repair", 15, 19, 50),
};
System.out.println("At most: " + "€" + bestPay(jobs));

At most: €220

static int bestPay(Job[] jobs) {
    Arrays.sort(jobs, Comparator.comparingInt(Job::end));
    int n = jobs.length;
    int[] best = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        Job job = jobs[i - 1];
        int p = 0;
        while (jobs[p].end() <= job.start()) p++;
        int skip = best[i - 1];
        int take = job.pay() + best[p];
        best[i] = Math.max(skip, take);
    }
    return best[n];
}

Step by step, in words

Six requests for one van. State: sort them by end; best[i] is the most money from the first i.
Base: best[0] = 0, no requests, no money. Order: left to right, every cell needs only cells to its left.
Request 1, market 8–10, €60: no request ends before it starts, p = 0. Skip: best[0] = 0. Take: 60 + best[0] = 60. Better to take it: best[1] = 60.
Request 2, sofa 9–12, €80: no request ends before it starts, p = 0. Skip: best[1] = 60. Take: 80 + best[0] = 80. Better to take it: best[2] = 80.
Request 3, office 11–13, €60: one ends by 11:00, p = 1. Skip: best[2] = 80. Take: 60 + best[1] = 120. Better to take it: best[3] = 120.
Request 4, depot 12–17, €30: 2 end by 12:00, p = 2. Skip: best[3] = 120. Take: 30 + best[2] = 110. Better to skip it: best[4] = 120.
Request 5, repair 15–19, €50: 3 end by 15:00, p = 3. Skip: best[4] = 120. Take: 50 + best[3] = 170. Better to take it: best[5] = 170.
Request 6, airport 15–20, €100: 3 end by 15:00, p = 3. Skip: best[5] = 170. Take: 100 + best[3] = 220. Better to take it: best[6] = 220.
Answer: best[6] = €220. Following “take” back from it gives the requests: market, office, airport.

€220 from market, office and airport: more than both the most expensive first and the earliest end first.

Try it

Find the bug

A colleague copied the transition. The program says:

static int bestPay(Job[] jobs) {
    Arrays.sort(jobs, Comparator.comparingInt(Job::end));
    int n = jobs.length;
    int[] best = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        Job job = jobs[i - 1];
        int p = 0;
        while (jobs[p].end() <= job.start()) p++;
        int skip = best[i - 1];
        int take = job.pay() + best[i - 1];
        best[i] = Math.max(skip, take);
    }
    return best[n];
}

Job[] jobs = {
    new Job("sofa", 9, 12, 80),
    new Job("airport", 15, 20, 100),
    new Job("market", 8, 10, 60),
    new Job("depot", 12, 17, 30),
    new Job("office", 11, 13, 60),
    new Job("repair", 15, 19, 50),
};
System.out.println("At most: " + "€" + bestPay(jobs));

At most: €380

That is impossible: all six requests together do not fit in one van. Which line is the bug on?

Pick the line with the bug.

The idea

A second task: parking along the route

A truck drives from the depot to the last parking stop on the motorway. The driver must rest: from one stop he reaches at most the next or the one after it. Every stop has a fee. How little will he pay, stopping at the last one too?

The signs: "how little", and the cheapest way to stop i goes through the cheapest way to i − 1 or to i − 2. The recipe:

State: cost[i] is the least paid up to stop i, stopping at it.
Transition: cost[i] = the fee of i + min(cost[i − 1], cost[i − 2]).
Base: from the depot he reaches stop 0 or goes straight to stop 1, so cost[0] and cost[1] are just their fees.
Order: left to right.
Answer: cost of the last stop.

static int minFees(int[] fee) {
    int n = fee.length;
    int[] cost = new int[n];
    cost[0] = fee[0];
    cost[1] = fee[1];
    for (int i = 2; i < n; i++) {
        cost[i] = fee[i] + Math.min(cost[i - 1], cost[i - 2]);
    }
    return cost[n - 1];
}

int[] parking = {4, 9, 3, 12, 5, 2, 10, 6};
System.out.println("At least: " + "€" + minFees(parking));

At least: €20

Try it

Predict the output

Four parking stops with fees of €5, €1, €4 and €2:

static int minFees(int[] fee) {
    int n = fee.length;
    int[] cost = new int[n];
    cost[0] = fee[0];
    cost[1] = fee[1];
    for (int i = 2; i < n; i++) {
        cost[i] = fee[i] + Math.min(cost[i - 1], cost[i - 2]);
    }
    return cost[n - 1];
}

int[] parking = {5, 1, 4, 2};
System.out.println("At least: " + "€" + minFees(parking));

Answer

At least: €8

At least: €12

At least: €3

The idea

A third task: text without spaces

Customers type "summersale" into the search box, without spaces, as in a hashtag. Can the text be split into dictionary words?

The sign is "is it possible": yes or no. The recipe:

State: ok[i] is "the first i letters split into words".
Transition: ok[i] is true if there is a j < i with ok[j] and the letters from j to i are a dictionary word.
Base: ok[0] is true: the empty beginning always splits.
Order: i grows.
Answer: ok[n].

static boolean canSplit(String text, Set<String> words) {
    int n = text.length();
    boolean[] ok = new boolean[n + 1];
    ok[0] = true;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i && !ok[i]; j++) {
            ok[i] = ok[j] && words.contains(text.substring(j, i));
        }
    }
    return ok[n];
}

Set<String> words = Set.of(
    "summer", "sum", "sale", "sales", "shoe", "shoes", "for", "kids", "kid");
for (String text : List.of("summersale", "shoesforkids", "shoesforbabies")) {
    System.out.println(text + ": " + (canSplit(text, words) ? "yes" : "no"));
}

summersale: yes
shoesforkids: yes
shoesforbabies: no

More precisely, if you are curious

For every i the loop tries up to i places for j, and every piece is cut out and looked up in the dictionary. Cutting copies the letters (substring makes a new string), so the whole is up to O(n³) for a text of n letters. If the longest dictionary word has L letters, j only needs to be between i − L and i, and the time drops to O(n · L²). Real search engines use a trie of the dictionary words: they walk the letters from j onwards and stop as soon as the trie ends.

Try it

Fill in the transition

static boolean canSplit(String text, Set<String> words) {
    int n = text.length();
    boolean[] ok = new boolean[n + 1];
    ok[0] = true;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i && !ok[i]; j++) {
            ok[i] = ;
        }
    }
    return ok[n];
}

The idea

Looks like DP, but is not

Not every "most" task needs a table.

Greedy is sometimes enough. If all van requests pay the same, the question becomes "how many requests at most", and the rule "earliest end first" gives exactly the best, in O(n log n) and without a table. When greedy is provably right and why is in the next module. The sign: at every step one choice is always at least as good as any other.
The graph has no order. The shortest path in a city looks like DP: the distance to a crossing is built from the distances to its neighbours. But the streets form loops, and "to A" depends on "to B", while "to B" depends on "to A". There is no order in which to fill the table from left to right. That is why it is Dijkstra there: it finds the order on the move.
No overlap. If the subproblems do not repeat, as in merge sort, remembering saves nothing. That is divide and conquer.

The test is step 4 of the recipe: if you cannot say in what order to fill, the task is probably about a graph.

Exercise

The billboards

Solve the task in your editor.

Billboards. Along the boulevard there are seven billboards, numbered from 1, with a monthly rent of €120, €90, €60, €150, €80, €40 and €130. Two neighbouring boards hide each other, so both cannot be rented out. Write the solution by the recipe: print the biggest rent and which boards to rent out:

At most: €400
Boards: 1, 4, 7

Hint: the state is "the most from the first i boards", and the transition is the same choice as for the van: skip board i or take it together with the best up to i − 2.

More tasks

How many ways. In how many ways can the truck reach the last parking stop (one or two stops at a time)? Only the transition changes: a sum instead of a minimum.
The split by name. Also print the words of "summersale": keep for every ok[i] where it came from.
The requests by name. Make bestPay also return which requests to accept: walk back from best[n], as in the scene.

Test

Check yourself

1. Which question is most likely a DP task?How few coins of 1, 3 and 4 cents make 6 cents?Sort the products by priceIs there an order with number 1042 in the list?

2. In the van task the requests are sorted by end. Why?Without sorting the program does not compileBecause the greedy rule does it tooThen the requests that end before the i-th one are the first ones in a row: best[p] covers them

3. What is the base for the text without spaces?ok[0] = true: the empty text always splitsok[n] = trueok[0] = false

4. Why is the shortest path in the city with Dijkstra not written as a table from left to right?The streets form loops: there is no order in which every cell depends only on finished cellsBecause the table would be too bigBecause Dijkstra does not look for the shortest

5. Do you miss something if the transition is take = pay + best[i − 1]?Yes: you lose the base best[0]No, it is only slowerYes: you may take a request that overlaps one already taken

How to recognise a DP task

Cookies