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

Код на:JavaC#PythonJavaScript

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

Проблем

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

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

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

static long calls = 0;

static int[] fees(int n) {
    int[] fee = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        fee[i] = 40 + (i * 37) % 90;
    }
    return fee;
}

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

for (int km : new int[] {10, 30}) {
    calls = 0;
    int cost = cheapest(fees(km), km);
    System.out.println(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… Функцията има същата форма, двете по-малки и събиране:

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

Изход

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

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

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

Виж го

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

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

static int cheapestMemo(int[] fee, int i, int[] memo) {
    if (i <= 1) {
        return fee[i];
    }
    if (memo[i] != -1) {
        return memo[i];
    }
    int oneBack = cheapestMemo(fee, i - 1, memo);
    int twoBack = cheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.min(oneBack, twoBack);
    return memo[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, върни записаното.

static long calls = 0;

static int[] fees(int n) {
    int[] fee = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        fee[i] = 40 + (i * 37) % 90;
    }
    return fee;
}

static int cheapestMemo(int[] fee, int i, int[] memo) {
    calls++;
    if (i <= 1) {
        return fee[i];
    }
    if (memo[i] != -1) {
        return memo[i];
    }
    int oneBack = cheapestMemo(fee, i - 1, memo);
    int twoBack = cheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.min(oneBack, twoBack);
    return memo[i];
}

int[] fee = fees(30);
int[] memo = new int[fee.length];
Arrays.fill(memo, -1);
int cost = cheapestMemo(fee, 30, memo);
System.out.println(cost + " цента, " + calls + " извиквания");

Изход

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

Паметта е масив с по едно място за всеки километър. -1 значи „още не е сметнато“: таксите са положителни, затова истински отговор никога не е -1.

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

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

Пробвай

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

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

static long calls = 0;

static int[] fees(int n) {
    int[] fee = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        fee[i] = 40 + (i * 37) % 90;
    }
    return fee;
}

static int cheapestMemo(int[] fee, int i, int[] memo) {
    calls++;
    if (i <= 1) {
        return fee[i];
    }
    if (memo[i] != -1) {
        return memo[i];
    }
    int oneBack = cheapestMemo(fee, i - 1, memo);
    int twoBack = cheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.min(oneBack, twoBack);
    return memo[i];
}

int[] fee = fees(8);
int[] memo = new int[fee.length];
Arrays.fill(memo, -1);
int cost = cheapestMemo(fee, 8, memo);
System.out.println(cost + " цента, " + calls + " извиквания");

Отговор

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

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

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

Провери

Идеята

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

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

static int cheapestTable(int[] fee) {
    int n = fee.length - 1;
    int[] best = new int[n + 1];
    best[0] = fee[0];
    best[1] = fee[1];
    for (int i = 2; i <= n; i++) {
        int 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. Всичко преди тях вече не трябва. Затова цялата таблица може да стане две променливи, които се плъзгат напред:

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

int[] fee = fees(30);
System.out.println("таблица: " + cheapestTable(fee) + " цента");
System.out.println("две променливи: " + 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 не пускаме, за да не замръзне страницата.

static int cheapestMemo(int[] fee, int i, int[] memo) {
    if (i <= 1) {
        return fee[i];
    }
    if (memo[i] != -1) {
        return memo[i];
    }
    int oneBack = cheapestMemo(fee, i - 1, memo);
    int twoBack = cheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.min(oneBack, twoBack);
    return memo[i];
}

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

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

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

static long calls = 0;
static long cells = 0;

static int[] fees(int n) {
    int[] fee = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        fee[i] = 40 + (i * 37) % 90;
    }
    return fee;
}

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

static int cheapestMemo(int[] fee, int i, int[] memo) {
    calls++;
    if (i <= 1) {
        return fee[i];
    }
    if (memo[i] != -1) {
        return memo[i];
    }
    int oneBack = cheapestMemo(fee, i - 1, memo);
    int twoBack = cheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.min(oneBack, twoBack);
    return memo[i];
}

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

for (int km : new int[] {10, 20, 30}) {
    int[] fee = fees(km);
    calls = 0;
    cheapest(fee, km);
    long plain = calls;
    calls = 0;
    int[] memo = new int[fee.length];
    Arrays.fill(memo, -1);
    cheapestMemo(fee, km, memo);
    cells = 0;
    int cost = cheapestTable(fee);
    System.out.println(km + " км: " + plain + " / " + calls + " / " + cells + ", " + cost + " цента");
}

Изход

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

Пробвай

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

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

int[] fee = fees(30);
int[] memo = new int[fee.length];
Arrays.fill(memo, -1);
int cost = cheapestMemo(fee, 30, memo);
System.out.println(cost + " цента, " + calls + " извиквания");

Изход

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

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

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

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

Провери

Пробвай

Попълни

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

static int cheapestTable(int[] fee) {
    int n = fee.length - 1;
    int[] best = new int[n + 1];
    best[0] = fee[0];
    best[1] = fee[1];
    for (int i = 2; i <= n; i++) {
        int 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 рамки, както в урока за стека. Таблицата прави същата работа в цикъл, и стекът не расте, както в от рекурсия към цикъл.

static int[] fees(int n) {
    int[] fee = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        fee[i] = 40 + (i * 37) % 90;
    }
    return fee;
}

static int cheapestMemo(int[] fee, int i, int[] memo) {
    if (i <= 1) {
        return fee[i];
    }
    if (memo[i] != -1) {
        return memo[i];
    }
    int oneBack = cheapestMemo(fee, i - 1, memo);
    int twoBack = cheapestMemo(fee, i - 2, memo);
    memo[i] = fee[i] + Math.min(oneBack, twoBack);
    return memo[i];
}

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

int[] fee = fees(1000000);
try {
    int[] memo = new int[fee.length];
    Arrays.fill(memo, -1);
    cheapestMemo(fee, 1000000, memo);
} catch (StackOverflowError e) {
    System.out.println("cheapestMemo: StackOverflowError");
}
System.out.println("cheapestTable: " + cheapestTable(fee));

Изход

cheapestMemo: StackOverflowError
cheapestTable: 38866659

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

Паметта, вградена в езика. В Java е изкусително да напишеш паметта като memo.computeIfAbsent(i, k -> fee[k] + Math.min(...)) с рекурсия вътре. Не го прави с HashMap: рекурсивно извикване, което променя същата таблица по време на computeIfAbsent, хвърля ConcurrentModificationException (от Java 9). Масивът или containsKey + put са сигурни.

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

Тест

Провери се

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 задача
• Задачи по темата: Динамично програмиране