Припокриващи се подзадачи

Код на:JavaC#PythonJavaScript

Накратко: Динамичното програмиране решава всяка подзадача веднъж и пази отговора: с memoization отгоре надолу или с таблица отдолу нагоре, вместо рекурсия, която решава едно и също отново.

Проблем

Планът за зареждане

Куриерът кара електрическа тротинетка по маршрут от n км. На всеки километър има станция за зареждане, а батерията стига за най-много 2 км. Значи от всяка спирка той продължава с 1 или 2 км до следващата. На всяка станция, където спре, плаща таксата ѝ. Таксите са различни, и приложението трябва да намери най-евтиния план.

Първото решение мисли назад. Последната спирка е км n. Преди нея куриерът е бил на км n − 1 или на км n − 2. Значи най-евтиното до n е таксата на n плюс по-евтиното от двете: най-евтиното до n − 1 и най-евтиното до n − 2. Това е рекурсия, като в урока „Рекурсия“. Таксите са в центове, а броячът казва колко пъти функцията е извикана:

let calls = 0;

function fees(n) {
  const fee = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    fee[i] = 40 + ((i * 37) % 90);
  }
  return fee;
}

function cheapest(fee, i) {
  calls++;
  if (i <= 1) {
    return fee[i];
  }
  const oneBack = cheapest(fee, i - 1);
  const twoBack = cheapest(fee, i - 2);
  return fee[i] + Math.min(oneBack, twoBack);
}

for (const km of [10, 30]) {
  calls = 0;
  const cost = cheapest(fees(km), km);
  console.log(`${km} км: ${cost} цента, ${calls} извиквания`);
}

Изход

10 км: 381 цента, 177 извиквания
30 км: 1217 цента, 2692537 извиквания

Отговорът е верен, но за 30 км функцията е извикана 2 692 537 пъти. За 50 км би била извикана 40 730 022 147 пъти: при милиард извиквания в секунда това е повече от половин минута, а маршрутът на куриер е и по 100 км.

Идеята

Един и същ въпрос, зададен милиони пъти

Защо толкова много? Проследи кой какво пита. Най-евтиното до км 30 пита за км 29 и км 28. Км 29 пита за 28 и 27. Км 28 е питан два пъти, и всеки път се смята отначало, заедно с всичко под него. Надолу повторенията се трупат: км 27 е питан три пъти, км 26 пет пъти.

Чистият пример за това са числата на Фибоначи: всяко е сборът на предишните две, 0, 1, 1, 2, 3, 5, 8… Функцията има същата форма, двете по-малки и събиране:

function fib(n) {
  calls++;
  if (n <= 1) {
    return n;
  }
  return fib(n - 1) + fib(n - 2);
}

Изход

fib(30) = 832040, 2692537 извиквания

Броят извиквания е същият до последната цифра, защото дървото на извикванията е същото. А планът е само едно от многото места с това дърво.

Такива подзадачи се казват припокриващи се: една и съща по-малка задача е нужна на няколко по-големи. В „разделяй и владей“ не е така. Merge sort дели поръчките на две половини, които нямат нито една обща поръчка, и всяко парче се решава веднъж. Тук „най-евтиното до км 28“ е нужно и на км 29, и на км 30.

Виж го

Дървото и паметта

Цялото дърво на извикванията за 6 км, после същото, но с памет. Гледай кои кутии се повтарят и какво става с тях, когато отговорът им е запомнен:

function cheapestMemo(fee, i, memo) {
  if (i <= 1) {
    return fee[i];
  }
  if (memo.has(i)) {
    return memo.get(i);
  }
  const oneBack = cheapestMemo(fee, i - 1, memo);
  const twoBack = cheapestMemo(fee, i - 2, memo);
  memo.set(i, fee[i] + Math.min(oneBack, twoBack));
  return memo.get(i);
}

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

1. Всяка кутия е едно извикване cheapest(k): най-евтиното до км k. cheapest(6) пита за 5 и 4, а всяко от тях пита за още две по-малки.
2. Дървото спира на км 1 и 0, където отговорът е самата такса. За 6 км това са 25 извиквания.
3. Едни и същи въпроси отново и отново: cheapest(4) два пъти, cheapest(3) три пъти, cheapest(2) пет пъти. Подзадачите се припокриват.
4. С памет: извикванията вървят в същия ред, а първия път, когато отговорът е сметнат, той влиза в memo отдолу.
5. Вторият път отговорът вече е в memo (зелено): цялото поддърво под него изобщо не се пуска. 11 извиквания вместо 25.
6. Таблица отдолу нагоре: best[0] и best[1] са таксите, а всяка следваща клетка се строи от двете преди нея. 5 клетки, без рекурсия.
7. Всяка клетка иска само последните две. Две променливи се плъзгат напред вместо таблицата: O(n) време и O(1) памет.

Идеята

Запомни отговора

Поправката е да не смяташ два пъти едно и също. Първия път, когато смяташ най-евтиното до км k, запиши го. Следващия път, когато някой пита за k, върни записаното.

let calls = 0;

function fees(n) {
  const fee = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    fee[i] = 40 + ((i * 37) % 90);
  }
  return fee;
}

function cheapestMemo(fee, i, memo) {
  calls++;
  if (i <= 1) {
    return fee[i];
  }
  if (memo.has(i)) {
    return memo.get(i);
  }
  const oneBack = cheapestMemo(fee, i - 1, memo);
  const twoBack = cheapestMemo(fee, i - 2, memo);
  memo.set(i, fee[i] + Math.min(oneBack, twoBack));
  return memo.get(i);
}

const fee = fees(30);
const memo = new Map();
const cost = cheapestMemo(fee, 30, memo);
console.log(`${cost} цента, ${calls} извиквания`);

Изход

1217 цента, 59 извиквания

Паметта е Map: ключът е километърът, стойността е отговорът. memo.has(i) казва дали вече е сметнато.

Това се казва memoization (запомняне на резултатите). Функцията е същата рекурсия, само че с памет. 59 извиквания вместо 2 692 537: всеки километър се смята веднъж, а второто питане за него връща готовото.

Задача, която се сглобява от отговорите на по-малки задачи, когато тези по-малки се повтарят, се решава с динамично програмиране: всяка подзадача се решава веднъж и отговорът ѝ се пази. Името е старо и не казва много. Запомни го като „запомни и използвай пак“.

Пробвай

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

Същата функция с памет, за маршрут от 8 км. Колко пъти ще бъде извикана?

let calls = 0;

function fees(n) {
  const fee = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    fee[i] = 40 + ((i * 37) % 90);
  }
  return fee;
}

function cheapestMemo(fee, i, memo) {
  calls++;
  if (i <= 1) {
    return fee[i];
  }
  if (memo.has(i)) {
    return memo.get(i);
  }
  const oneBack = cheapestMemo(fee, i - 1, memo);
  const twoBack = cheapestMemo(fee, i - 2, memo);
  memo.set(i, fee[i] + Math.min(oneBack, twoBack));
  return memo.get(i);
}

const fee = fees(8);
const memo = new Map();
const cost = cheapestMemo(fee, 8, memo);
console.log(`${cost} цента, ${calls} извиквания`);

Отговор

331 цента, 67 извиквания

331 цента, 15 извиквания

331 цента, 8 извиквания

Провери

Идеята

Отдолу нагоре

Рекурсията с памет тръгва от км n и слиза надолу, докато стигне до малките. Може и обратно: започни от малките и се качвай. Най-евтиното до км 0 и км 1 е самата такса. От тях следва км 2, после км 3, и така до n. Когато стигнеш до клетка, двете под нея вече са готови.

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

Това е динамично програмиране отдолу нагоре, с таблица. Няма рекурсия и няма проверка „сметнато ли е“: редът на цикъла гарантира, че всичко нужно е вече в таблицата. Клетките са n − 1, по една работа на клетка: O(n).

И още едно наблюдение. Клетка i гледа само i − 1 и i − 2. Всичко преди тях вече не трябва. Затова цялата таблица може да стане две променливи, които се плъзгат напред:

function cheapestPair(fee) {
  let twoBack = fee[0];
  let oneBack = fee[1];
  for (let i = 2; i < fee.length; i++) {
    const here = fee[i] + Math.min(oneBack, twoBack);
    twoBack = oneBack;
    oneBack = here;
  }
  return oneBack;
}

const fee = fees(30);
console.log(`таблица: ${cheapestTable(fee)} цента`);
console.log(`две променливи: ${cheapestPair(fee)} цента`);

Изход

таблица: 1217 цента
две променливи: 1217 цента

Времето е пак O(n), а паметта O(1): две числа, колкото и дълъг да е маршрутът.

Виж го

Измери го: без памет, с памет, с таблица

Пусни трите върху маршрути от 10, 20 и 30 км. Броим извикванията на функцията, а при таблицата клетките. По-далеч от 30 км рекурсията без памет не се пуска: при 40 км са 331 160 281 извиквания и страницата ще замръзне.

• Рекурсия без памет O(2ⁿ)
• Рекурсия с памет O(n)
• Таблица отдолу нагоре O(n)

Алгоритъм	n = 10	n = 20	n = 30
Рекурсия без памет	177	21 891	2 692 537
Рекурсия с памет	19	39	59
Таблица отдолу нагоре	9	19	29

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

function cheapestMemo(fee, i, memo) {
  if (i <= 1) {
    return fee[i];
  }
  if (memo.has(i)) {
    return memo.get(i);
  }
  const oneBack = cheapestMemo(fee, i - 1, memo);
  const twoBack = cheapestMemo(fee, i - 2, memo);
  memo.set(i, fee[i] + Math.min(oneBack, twoBack));
  return memo.get(i);
}

Всеки 10 км умножават рекурсията без памет около 123 пъти, а другите две растат с по 20 и по 10. Кривата на Bench е с етикет O(2ⁿ): тя е експоненциална, с основа около 1,6, колкото е отношението между две съседни числа на Фибоначи.

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

Същите числа на твоя език: извикванията без памет, с памет и клетките на таблицата за 10, 20 и 30 км.

let calls = 0;
let cells = 0;

function fees(n) {
  const fee = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    fee[i] = 40 + ((i * 37) % 90);
  }
  return fee;
}

function cheapest(fee, i) {
  calls++;
  if (i <= 1) {
    return fee[i];
  }
  const oneBack = cheapest(fee, i - 1);
  const twoBack = cheapest(fee, i - 2);
  return fee[i] + Math.min(oneBack, twoBack);
}

function cheapestMemo(fee, i, memo) {
  calls++;
  if (i <= 1) {
    return fee[i];
  }
  if (memo.has(i)) {
    return memo.get(i);
  }
  const oneBack = cheapestMemo(fee, i - 1, memo);
  const twoBack = cheapestMemo(fee, i - 2, memo);
  memo.set(i, fee[i] + Math.min(oneBack, twoBack));
  return memo.get(i);
}

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

for (const km of [10, 20, 30]) {
  const fee = fees(km);
  calls = 0;
  cheapest(fee, km);
  const plain = calls;
  calls = 0;
  cheapestMemo(fee, km, new Map());
  cells = 0;
  const cost = cheapestTable(fee);
  console.log(`${km} км: ${plain} / ${calls} / ${cells}, ${cost} цента`);
}

Изход

10 км: 177 / 19 / 9, 381 цента
20 км: 21891 / 39 / 19, 822 цента
30 км: 2692537 / 59 / 29, 1217 цента

Пробвай

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

Колега е написал функцията с памет. Отговорът е верен, но броячът показва същото като без памет:

const fee = fees(30);
const memo = new Map();
const cost = cheapestMemo(fee, 30, memo);
console.log(`${cost} цента, ${calls} извиквания`);

Изход

1217 цента, 2692537 извиквания

На кой ред е грешката?

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

1function cheapestMemo(fee, i, memo) {2 if (i <= 1) {3 return fee[i];4 }5 if (memo.has(i)) {6 return memo.get(i);7 }8 const oneBack = cheapestMemo(fee, i - 1, memo);9 const twoBack = cheapestMemo(fee, i - 2, memo);10 return fee[i] + Math.min(oneBack, twoBack);11}

Провери

Пробвай

Попълни

Клетка i в таблицата е таксата на км i плюс по-евтиното от двете места, от които може да се дойде. Кое е второто?

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

Провери

Упражнение

Таксите от входа

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

Най-евтиният план. Прочети таксите на станциите от км 1 до км n (в центове, разделени с интервал) и отпечатай най-евтиния план. Ползвай cheapestPair от урока.

Вход

77 114 61 98 45 82

Изход

Най-евтино: 265 цента

Още задачи

• Кои станции. Отпечатай и самите километри, на които куриерът спира. Подсказка: до таблицата пази и откъде е дошъл (от i − 1 или от i − 2), после тръгни от n назад.
• Колко плана има. Преброй всички планове, без значение колко струват. Колко са за 30 км? Сравни числата с тези на Фибоначи. (За 30 км са 1 346 269.)
• По-добра батерия. Новата тротинетка стига за 3 км. Как се сменя формулата, и колко променливи трябват вместо две?

По-точно

Дълбочината и вградената памет

Паметта сваля работата, но рекурсията си остава рекурсия.

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

Колко дълбоко слиза. Рекурсията с памет първо слиза по веригата n, n − 1, … 1, и чак тогава почва да записва. Стекът от извиквания е n рамки, както в урока за стека. Таблицата прави същата работа в цикъл, и стекът не расте, както в от рекурсия към цикъл.

function fees(n) {
  const fee = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    fee[i] = 40 + ((i * 37) % 90);
  }
  return fee;
}

function cheapestMemo(fee, i, memo) {
  if (i <= 1) {
    return fee[i];
  }
  if (memo.has(i)) {
    return memo.get(i);
  }
  const oneBack = cheapestMemo(fee, i - 1, memo);
  const twoBack = cheapestMemo(fee, i - 2, memo);
  memo.set(i, fee[i] + Math.min(oneBack, twoBack));
  return memo.get(i);
}

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

const fee = fees(100000);
try {
  cheapestMemo(fee, 100000, new Map());
} catch (e) {
  console.log("cheapestMemo:", e.constructor.name);
}
console.log("cheapestTable:", cheapestTable(fee));

Изход

cheapestMemo: RangeError
cheapestTable: 3886659

Java и JavaScript нямат лимит в брой нива, но стекът е около 1 MB, и 100 000 вложени извиквания не се събират. В Python лимитът е 1000 нива.

Паметта, вградена в езика. В JavaScript няма вградена памет за функции. Map е правилният избор: обикновен обект превръща ключовете в низове, а Map пази числото като число. За ключ от няколко числа се ползва низ, например `${i},${j}`.

Отгоре надолу или отдолу нагоре. Двата начина решават едни и същи подзадачи. С памет смята само тези, до които наистина се стига, и се пише направо от наивната рекурсия. С таблица няма рекурсия и често може да се свие като тук. Ако подзадачите са много, а отговорът иска малко от тях, паметта печели. Ако трябват почти всички, таблицата е по-бърза и не рискува стека.

Тест

Провери се

1. Защо рекурсията без памет за 30 км прави 2,7 милиона извиквания, а с памет 59?

С памет функцията прескача километрите, които не са нужниБез памет едни и същи подзадачи (най-евтиното до км 5, до км 4…) се решават отново всеки път, когато някой пита за тяхПаметта прави всяко извикване по-бързо

2. По какво динамичното програмиране се различава от „разделяй и владей“ в merge sort?

Merge sort ползва таблица, а динамичното програмиране неДинамичното програмиране винаги дели наполовинаВ merge sort половините не се застъпват и всяка подзадача се решава веднъж и без памет; тук подзадачите се повтарят и си струва да се запомнят

3. Таблицата за n км се пълни от best[2] до best[n]. Колко памет иска версията с две променливи?

O(log n)O(1): само последните две стойностиO(n): цялата таблица

4. Функция с памет проверява паметта, но никъде не записва в нея. Какво става?

Функцията не спираОтговорът излиза грешенОтговорът е верен, но извикванията са колкото без памет

5. Защо в Python рекурсията с памет пада за 5000 км, а таблицата минава?

Таблицата ползва по-малки числаПаметта на Python не стига за 5000 числаС памет първото извикване слиза 5000 нива надолу преди да запише нещо, а лимитът на Python е 1000 нива; таблицата е цикъл без рекурсия

Провери

Започни урока отначало

Свързани уроци

• Нужно отпреди: Merge sort и „разделяй и владей“ · Стекът от извиквания отвътре · От рекурсия към цикъл · Разделяй и владей и дървото на рекурсията
• Продължава в: Задачата за монетите · Задачата за раницата · Най-дълга обща подредица и diff · Как да разпознаеш DP задача
• Задачи по темата: Динамично програмиране