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

Проблем

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

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

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

static List<Job> Greedy(Job[] jobs, Func<Job, int> rule)
{
    var taken = new List<Job>();
    foreach (var job in jobs.OrderBy(rule))
    {
        bool free = taken.All(t => job.End <= t.Start || t.End <= job.Start);
        if (free) taken.Add(job);
    }
    return taken;
}

static void Show(string rule, List<Job> taken)
{
    int sum = taken.Sum(t => t.Pay);
    var names = string.Join(", ", taken.Select(t => t.Name));
    Console.WriteLine($"{rule}: {names} = " + $"{sum} €");
}

Show("Най-скъпите първо", Greedy(jobs, job => -job.Pay));
Show("Най-ранният край първо", Greedy(jobs, job => 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) и запомня резултата (виж запомнянето). Таблицата отдолу нагоре и рекурсията с памет смятат едни и същи клетки. Рекурсията е по-близо до думите на прехода, таблицата няма дълбок стек.

В C# запомнянето е Dictionary<int, int> или масив с -1 за „още не е смятано“. Препълването на стека спира целия процес, затова за дълги редици таблицата е по-сигурна.

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

Виж го

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

static int BestPay(Job[] jobs)
{
    jobs = jobs.OrderBy(job => job.End).ToArray();
    int n = jobs.Length;
    var best = new int[n + 1];
    for (int i = 1; i <= n; i++)
    {
        var 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];
}

OrderBy прави нов подреден масив, а входът остава какъвто е. Цикълът за p спира най-късно на самата i-та заявка, защото тя свършва след началото си.

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

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

static int BestPay(Job[] jobs)
{
    jobs = jobs.OrderBy(job => job.End).ToArray();
    int n = jobs.Length;
    var best = new int[n + 1];
    for (int i = 1; i <= n; i++)
    {
        var 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)
{
    jobs = jobs.OrderBy(job => job.End).ToArray();
    int n = jobs.Length;
    var best = new int[n + 1];
    for (int i = 1; i <= n; i++)
    {
        var 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("мебели", 9, 12, 80),
    new("летище", 15, 20, 100),
    new("пазар", 8, 10, 60),
    new("склад", 12, 17, 30),
    new("офис", 11, 13, 60),
    new("ремонт", 15, 19, 50),
];
Console.WriteLine("Най-много: " + $"{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;
    var 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];
Console.WriteLine("Най-малко: " + $"{MinFees(parking)} €");

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

Пробвай

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

Четири паркинга с такси 5, 1, 4 и 2 €:

static int MinFees(int[] fee)
{
    int n = fee.Length;
    var 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];
Console.WriteLine("Най-малко: " + $"{MinFees(parking)} €");

Отговор

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

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

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

Идеята

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

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

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

Състояние: ok[i] е „първите i букви се разделят на думи“.
Преход: ok[i] е истина, ако има j < i с ok[j] и буквите от j до i са дума от речника.
Основа: ok[0] е истина: празното начало винаги се разделя.
Ред: i расте.
Отговор: ok[n].

static bool CanSplit(string text, HashSet<string> words)
{
    int n = text.Length;
    var ok = new bool[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[j..i]);
        }
    }
    return ok[n];
}

var words = new HashSet<string>
{
    "лятна", "лят", "на", "разпродажба", "раз", "продажба", "обувки", "за", "деца",
};
foreach (string text in new[] { "лятнаразпродажба", "обувкизадеца", "обувкизабебета" })
{
    Console.WriteLine(text + ": " + (CanSplit(text, words) ? "да" : "не"));
}

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

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

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

Пробвай

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

static bool CanSplit(string text, HashSet<string> words)
{
    int n = text.Length;
    var ok = new bool[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 задача

Бисквитки