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

Проблем

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

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

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

function greedy(jobs, rule) {
  const taken = [];
  for (const job of [...jobs].sort(rule)) {
    const free = taken.every((t) => job.end <= t.start || t.end <= job.start);
    if (free) taken.push(job);
  }
  return taken;
}

function show(rule, taken) {
  const sum = taken.reduce((s, job) => s + job.pay, 0);
  const names = taken.map((job) => job.name).join(", ");
  console.log(`${rule}: ${names} = ` + `${sum} €`);
}

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

В JavaScript запомнянето е Map или масив с undefined за „още не е смятано“. Около 10 000 вложени извиквания дават RangeError, затова за дълги редици таблицата е по-сигурна.

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

Виж го

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

function bestPay(jobs) {
  const sorted = [...jobs].sort((a, b) => a.end - b.end);
  const best = new Array(sorted.length + 1).fill(0);
  for (let i = 1; i <= sorted.length; i++) {
    const job = sorted[i - 1];
    let p = 0;
    while (sorted[p].end <= job.start) p++;
    const skip = best[i - 1];
    const take = job.pay + best[p];
    best[i] = Math.max(skip, take);
  }
  return best[sorted.length];
}

[...jobs].sort(...) подрежда копие, а входът остава какъвто е. Цикълът за p спира най-късно на самата i-та заявка, защото тя свършва след началото си.

const jobs = [
  { name: "мебели", start: 9, end: 12, pay: 80 },
  { name: "летище", start: 15, end: 20, pay: 100 },
  { name: "пазар", start: 8, end: 10, pay: 60 },
  { name: "склад", start: 12, end: 17, pay: 30 },
  { name: "офис", start: 11, end: 13, pay: 60 },
  { name: "ремонт", start: 15, end: 19, pay: 50 },
];
console.log("Най-много: " + `${bestPay(jobs)} €`);

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

function bestPay(jobs) {
  const sorted = [...jobs].sort((a, b) => a.end - b.end);
  const best = new Array(sorted.length + 1).fill(0);
  for (let i = 1; i <= sorted.length; i++) {
    const job = sorted[i - 1];
    let p = 0;
    while (sorted[p].end <= job.start) p++;
    const skip = best[i - 1];
    const take = job.pay + best[p];
    best[i] = Math.max(skip, take);
  }
  return best[sorted.length];
}

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

Шест заявки за един бус. Състояние: подреди ги по края; 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 € от пазар, офис и летище: повече и от най-скъпите първо, и от най-ранния край първо.

Пробвай

Намери грешката

Колега е преписал прехода. Програмата казва:

function bestPay(jobs) {
  const sorted = [...jobs].sort((a, b) => a.end - b.end);
  const best = new Array(sorted.length + 1).fill(0);
  for (let i = 1; i <= sorted.length; i++) {
    const job = sorted[i - 1];
    let p = 0;
    while (sorted[p].end <= job.start) p++;
    const skip = best[i - 1];
    const take = job.pay + best[i - 1];
    best[i] = Math.max(skip, take);
  }
  return best[sorted.length];
}

const jobs = [
  { name: "мебели", start: 9, end: 12, pay: 80 },
  { name: "летище", start: 15, end: 20, pay: 100 },
  { name: "пазар", start: 8, end: 10, pay: 60 },
  { name: "склад", start: 12, end: 17, pay: 30 },
  { name: "офис", start: 11, end: 13, pay: 60 },
  { name: "ремонт", start: 15, end: 19, pay: 50 },
];
console.log("Най-много: " + `${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 на последния паркинг.

function minFees(fee) {
  const cost = new Array(fee.length).fill(0);
  cost[0] = fee[0];
  cost[1] = fee[1];
  for (let i = 2; i < fee.length; i++) {
    cost[i] = fee[i] + Math.min(cost[i - 1], cost[i - 2]);
  }
  return cost[fee.length - 1];
}

const parking = [4, 9, 3, 12, 5, 2, 10, 6];
console.log("Най-малко: " + `${minFees(parking)} €`);

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

Пробвай

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

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

function minFees(fee) {
  const cost = new Array(fee.length).fill(0);
  cost[0] = fee[0];
  cost[1] = fee[1];
  for (let i = 2; i < fee.length; i++) {
    cost[i] = fee[i] + Math.min(cost[i - 1], cost[i - 2]);
  }
  return cost[fee.length - 1];
}

const parking = [5, 1, 4, 2];
console.log("Най-малко: " + `${minFees(parking)} €`);

Отговор

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

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

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

Идеята

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

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

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

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

function canSplit(text, words) {
  const n = text.length;
  const ok = new Array(n + 1).fill(false);
  ok[0] = true;
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i && !ok[i]; j++) {
      ok[i] = ok[j] && words.has(text.slice(j, i));
    }
  }
  return ok[n];
}

const words = new Set([
  "лятна", "лят", "на", "разпродажба", "раз", "продажба", "обувки", "за", "деца",
]);
for (const text of ["лятнаразпродажба", "обувкизадеца", "обувкизабебета"]) {
  console.log(text + ": " + (canSplit(text, words) ? "да" : "не"));
}

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

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

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

Пробвай

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

function canSplit(text, words) {
  const n = text.length;
  const ok = new Array(n + 1).fill(false);
  ok[0] = true;
  for (let i = 1; i <= n; i++) {
    for (let 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 задача

Бисквитки