Как да разпознаеш DP задача в Java

Проблем

Кои заявки да приеме бусът?

Имаш един бус под наем. За утре има шест заявки за превоз, всяка с начало, край и цена. Бусът може да е само на едно място, затова две заявки, които се застъпват, не може да се вземат и двете. Кои да приемеш, за да вземеш най-много?

Първото, което хрумва, е алчно правило: най-скъпата заявка първо, после следващата, която не пречи. Или: тази, която свършва най-рано, за да остане повече време:

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("Най-скъпите първо", greedy(jobs, Comparator.comparingInt(Job::pay).reversed()));
show("Най-ранният край първо", greedy(jobs, Comparator.comparingInt(Job::end)));

Най-скъпите първо: летище, мебели = 180 €
Най-ранният край първо: пазар, офис, ремонт = 170 €

И двете правила оставят пари на масата: има разписание за повече. Да пробваш всички 2⁶ = 64 подмножества тук става, но при 60 заявки те са над милиард милиарда. Задачата е от същия вид като раницата и diff. Как да го познаеш сам, и как да построиш решението?

Идеята

Признаците

Една задача е за динамично програмиране, когато има три неща:

Въпросът е за най-доброто или за броя. „Най-много“, „най-малко“, „колко начина“, „може ли изобщо“. Ако се пита само „намери елемента“ или „подреди“, няма какво да се избира.
Оптималната подструктура. Най-доброто решение на цялото се строи от най-добрите решения на по-малки части. При буса: ако последната заявка е в най-доброто разписание, останалото е най-доброто разписание на заявките, които свършват преди нея.
Припокриващите се подзадачи. Едни и същи по-малки части се питат много пъти, както при наивния Фибоначи. При буса и „ремонт“, и „летище“ започват в 15 ч. и питат за едно и също: най-многото от заявките, които свършват до 15 ч.

Щом трите ги има, отговорът на всяка малка част се смята веднъж и се записва.

Идеята

Рецептата в пет стъпки

Състояние. Какво е една клетка: „best[i] е най-много пари от първите i заявки, подредени по края“. Добро състояние описва малката задача с едно-две числа.
Преход. Как клетката се смята от по-малки. За заявка i има два избора: пропусни я (best[i − 1]) или вземи я (цената ѝ + best[p], където p е колко заявки свършват до началото ѝ). best[i] е по-голямото.
Основа. Клетките, които не зависят от нищо: best[0] = 0, без заявки няма пари.
Ред. В какъв ред да пълниш, така че нужното вече да е готово: отляво надясно, защото i ползва само i − 1 и p < i.
Отговор. Коя клетка е отговорът: best[n]. Ако искаш и кои заявки, вървиш назад по изборите, както обратния път в diff.

Подреждането по края е част от състоянието: така заявките, съвместими с i-тата, са точно първите p и „най-доброто от тях“ е една клетка.

По-точно, за любопитните

Същата рецепта работи и отгоре надолу: функция best(i), която вика best(i − 1) и best(p) и запомня резултата (виж запомнянето). Таблицата отдолу нагоре и рекурсията с памет смятат едни и същи клетки. Рекурсията е по-близо до думите на прехода, таблицата няма дълбок стек.

В Java запомнянето е Map<Integer, Integer> или масив с -1 за „още не е смятано“. Дълбока рекурсия може да хвърли StackOverflowError, затова за дълги редици таблицата е по-сигурна.

p може да се намери с двоично търсене по краищата, защото те са подредени: тогава цялото е O(n log n). Цикълът в урока е O(n) за всяка заявка, O(n²) общо, и за шест заявки е напълно достатъчен.

Виж го

Рецептата в код

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 подрежда масива на място, а Comparator.comparingInt(Job::end) казва по какво. Цикълът за p спира най-късно на самата i-та заявка, защото тя свършва след началото си.

Job[] jobs = {
    new Job("мебели", 9, 12, 80),
    new Job("летище", 15, 20, 100),
    new Job("пазар", 8, 10, 60),
    new Job("склад", 12, 17, 30),
    new Job("офис", 11, 13, 60),
    new Job("ремонт", 15, 19, 50),
};
System.out.println("Най-много: " + bestPay(jobs) + " €");

Най-много: 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];
}

Стъпка по стъпка, с думи

Шест заявки за един бус. Състояние: подреди ги по края; best[i] е най-много пари от първите i.
Основа: best[0] = 0, без заявки няма пари. Ред: отляво надясно, всяка клетка иска само клетки вляво от нея.
Заявка 1, пазар 8–10 ч., 60 €: нито една заявка не свършва преди нея, p = 0. Пропусни: best[0] = 0. Вземи: 60 + best[0] = 60. По-добре вземи я: best[1] = 60.
Заявка 2, мебели 9–12 ч., 80 €: нито една заявка не свършва преди нея, p = 0. Пропусни: best[1] = 60. Вземи: 80 + best[0] = 80. По-добре вземи я: best[2] = 80.
Заявка 3, офис 11–13 ч., 60 €: една свършва до 11 ч., p = 1. Пропусни: best[2] = 80. Вземи: 60 + best[1] = 120. По-добре вземи я: best[3] = 120.
Заявка 4, склад 12–17 ч., 30 €: 2 свършват до 12 ч., p = 2. Пропусни: best[3] = 120. Вземи: 30 + best[2] = 110. По-добре пропусни я: best[4] = 120.
Заявка 5, ремонт 15–19 ч., 50 €: 3 свършват до 15 ч., p = 3. Пропусни: best[4] = 120. Вземи: 50 + best[3] = 170. По-добре вземи я: best[5] = 170.
Заявка 6, летище 15–20 ч., 100 €: 3 свършват до 15 ч., p = 3. Пропусни: best[5] = 170. Вземи: 100 + best[3] = 220. По-добре вземи я: best[6] = 220.
Отговор: best[6] = 220 €. Назад по „вземи“ от нея излизат заявките: пазар, офис, летище.

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[i - 1];
        best[i] = Math.max(skip, take);
    }
    return best[n];
}

Job[] jobs = {
    new Job("мебели", 9, 12, 80),
    new Job("летище", 15, 20, 100),
    new Job("пазар", 8, 10, 60),
    new Job("склад", 12, 17, 30),
    new Job("офис", 11, 13, 60),
    new Job("ремонт", 15, 19, 50),
};
System.out.println("Най-много: " + bestPay(jobs) + " €");

Най-много: 380 €

Толкова не може: всички шест заявки заедно не се побират в един бус. На кой ред е грешката?

Избери реда с грешката.

Идеята

Втора задача: паркингите по пътя

Камион кара от склада до последния паркинг на магистралата. Шофьорът трябва да почива: от един паркинг стига най-много до следващия или по-следващия. Всеки паркинг има такса. Колко най-малко ще плати, като спре и на последния?

Признаците: „най-малко“, а най-евтиният път до паркинг i минава през най-евтиния път до i − 1 или до i − 2. Рецептата:

Състояние: cost[i] е най-малкото, платено до паркинг i, като спре на него.
Преход: cost[i] = таксата на i + min(cost[i − 1], cost[i − 2]).
Основа: от склада стига до паркинг 0 или направо до паркинг 1, затова cost[0] и cost[1] са само таксите им.
Ред: отляво надясно.
Отговор: cost на последния паркинг.

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("Най-малко: " + minFees(parking) + " €");

Най-малко: 20 €

Пробвай

Предвиди изхода

Четири паркинга с такси 5, 1, 4 и 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("Най-малко: " + minFees(parking) + " €");

Отговор

Най-малко: 12 €

Най-малко: 8 €

Най-малко: 3 €

Идеята

Трета задача: текст без интервали

Клиентите пишат в търсачката „лятнаразпродажба“, без интервали, както в хаштаг. Може ли текстът да се раздели на думи от речника?

Признакът е „може ли“: да или не. Рецептата:

Състояние: ok[i] е „първите i букви се разделят на думи“.
Преход: ok[i] е истина, ако има j < i с ok[j] и буквите от j до i са дума от речника.
Основа: ok[0] е истина: празното начало винаги се разделя.
Ред: i расте.
Отговор: 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(
    "лятна", "лят", "на", "разпродажба", "раз", "продажба", "обувки", "за", "деца");
for (String text : List.of("лятнаразпродажба", "обувкизадеца", "обувкизабебета")) {
    System.out.println(text + ": " + (canSplit(text, words) ? "да" : "не"));
}

лятнаразпродажба: да
обувкизадеца: да
обувкизабебета: не

По-точно, за любопитните

За всяко i цикълът пробва до i места за j, а всяко парче се изрязва и търси в речника. Изрязването копира буквите (substring прави нов низ), затова цялото е до O(n³) за текст с n букви. Ако най-дългата дума в речника е L букви, j трябва да е само между i − L и i, и времето пада до O(n · L²). Истинските търсачки ползват trie от думите на речника: вървят по буквите от j нататък и спират, щом trie-то свърши.

Пробвай

Попълни прехода

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];
}

Идеята

Прилича на DP, а не е

Не всяка задача за „най-много“ иска таблица.

Алчното понякога стига. Ако всички заявки за буса плащат еднакво, въпросът става „колко най-много заявки“, и правилото „най-ранният край първо“ дава точно най-доброто, за O(n log n) и без таблица. Кога алчното е доказано вярно и защо, е в следващия модул. Знакът: при всяка стъпка един избор е винаги поне толкова добър, колкото всеки друг.
Графът няма ред. Най-краткият път в града прилича на DP: разстоянието до кръстовище се строи от разстоянията до съседите. Но улиците правят кръгове, и „до A“ зависи от „до B“, а „до B“ от „до A“. Няма ред, в който да пълниш таблицата отляво надясно. Затова там е Dijkstra: той намира реда в движение.
Без припокриване. Ако подзадачите не се повтарят, както при merge sort, запомнянето не пести нищо. Това е „разделяй и владей“.

Проверката е стъпка 4 от рецептата: ако не можеш да кажеш в какъв ред да пълниш, задачата вероятно е за граф.

Упражнение

Рекламните табла

Реши задачата в редактора си.

Табла. По булеварда има седем рекламни табла, номерирани от 1, с месечен наем 120, 90, 60, 150, 80, 40 и 130 €. Две съседни табла се закриват едно друго, затова не може да се дадат под наем и двете. Напиши решението по рецептата: изведи най-големия наем и кои табла да се дадат:

Най-много: 400 €
Табла: 1, 4, 7

Подсказка: състоянието е „най-много от първите i табла“, а преходът е същият избор като при буса: пропусни табло i или го вземи заедно с най-доброто до i − 2.

Още задачи

Колко начина. По колко начина камионът може да стигне до последния паркинг (по един или два паркинга напред)? Сменя се само преходът: сума вместо минимум.
Разделянето поименно. Изведи и самите думи на „лятнаразпродажба“: пази за всяко ok[i] откъде е дошло.
Заявките поименно. Върни от bestPay и кои заявки да приемеш: вървиш назад от best[n], както на сцената.

Тест

Провери се

1. Кой въпрос най-вероятно е DP задача?Подреди продуктите по ценаИма ли в списъка поръчка с номер 1042?Колко най-малко монети от 1, 3 и 4 цента дават 6 цента?

2. В задачата с буса заявките се подреждат по края. Защо?Защото така прави и алчното правилоТогава заявките, които свършват преди i-тата, са поредните в началото: best[p] ги обхващаБез подреждане програмата не се компилира

3. Какво е основата при текста без интервали?ok[n] = trueok[0] = true: празният текст винаги се разделяok[0] = false

4. Защо най-краткият път в града с Dijkstra не се пише като таблица отляво надясно?Защото таблицата би била твърде голямаУлиците правят кръгове: няма ред, в който всяка клетка зависи само от готови клеткиЗащото Dijkstra не търси най-краткото

5. Пропускаш ли нещо, ако в прехода take = pay + best[i − 1]?Да: губиш основата best[0]Да: може да вземеш заявка, която се застъпва с вече взетаНе, само е по-бавно

Как да разпознаеш DP задача

Бисквитки