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

Код на:JavaC#PythonJavaScript

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

Проблем

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

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

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

calls = 0


def fees(n):
    return [0] + [40 + (i * 37) % 90 for i in range(1, n + 1)]


def cheapest(fee, i):
    global calls
    calls += 1
    if i <= 1:
        return fee[i]
    one_back = cheapest(fee, i - 1)
    two_back = cheapest(fee, i - 2)
    return fee[i] + min(one_back, two_back)


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

def fib(n):
    global calls
    calls += 1
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Изход

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

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

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

Виж го

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

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

def cheapest_memo(fee, i, memo):
    if i <= 1:
        return fee[i]
    if i in memo:
        return memo[i]
    one_back = cheapest_memo(fee, i - 1, memo)
    two_back = cheapest_memo(fee, i - 2, memo)
    memo[i] = fee[i] + min(one_back, two_back)
    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, върни записаното.

calls = 0


def fees(n):
    return [0] + [40 + (i * 37) % 90 for i in range(1, n + 1)]


def cheapest_memo(fee, i, memo):
    global calls
    calls += 1
    if i <= 1:
        return fee[i]
    if i in memo:
        return memo[i]
    one_back = cheapest_memo(fee, i - 1, memo)
    two_back = cheapest_memo(fee, i - 2, memo)
    memo[i] = fee[i] + min(one_back, two_back)
    return memo[i]


fee = fees(30)
memo = {}
cost = cheapest_memo(fee, 30, memo)
print(f"{cost} цента, {calls} извиквания")

Изход

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

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

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

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

Пробвай

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

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

calls = 0


def fees(n):
    return [0] + [40 + (i * 37) % 90 for i in range(1, n + 1)]


def cheapest_memo(fee, i, memo):
    global calls
    calls += 1
    if i <= 1:
        return fee[i]
    if i in memo:
        return memo[i]
    one_back = cheapest_memo(fee, i - 1, memo)
    two_back = cheapest_memo(fee, i - 2, memo)
    memo[i] = fee[i] + min(one_back, two_back)
    return memo[i]


fee = fees(8)
memo = {}
cost = cheapest_memo(fee, 8, memo)
print(f"{cost} цента, {calls} извиквания")

Отговор

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

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

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

Провери

Идеята

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

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

def cheapest_table(fee):
    n = len(fee) - 1
    best = [0] * (n + 1)
    best[0] = fee[0]
    best[1] = fee[1]
    for i in range(2, n + 1):
        cheaper = min(best[i - 1], best[i - 2])
        best[i] = fee[i] + cheaper
    return best[n]

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

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

def cheapest_pair(fee):
    two_back, one_back = fee[0], fee[1]
    for i in range(2, len(fee)):
        here = fee[i] + min(one_back, two_back)
        two_back, one_back = one_back, here
    return one_back

fee = fees(30)
print(f"таблица: {cheapest_table(fee)} цента")
print(f"две променливи: {cheapest_pair(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 не пускаме, за да не замръзне страницата.

def cheapest_memo(fee, i, memo):
    if i <= 1:
        return fee[i]
    if i in memo:
        return memo[i]
    one_back = cheapest_memo(fee, i - 1, memo)
    two_back = cheapest_memo(fee, i - 2, memo)
    memo[i] = fee[i] + min(one_back, two_back)
    return memo[i]

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

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

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

calls = 0
cells = 0


def fees(n):
    return [0] + [40 + (i * 37) % 90 for i in range(1, n + 1)]


def cheapest(fee, i):
    global calls
    calls += 1
    if i <= 1:
        return fee[i]
    one_back = cheapest(fee, i - 1)
    two_back = cheapest(fee, i - 2)
    return fee[i] + min(one_back, two_back)


def cheapest_memo(fee, i, memo):
    global calls
    calls += 1
    if i <= 1:
        return fee[i]
    if i in memo:
        return memo[i]
    one_back = cheapest_memo(fee, i - 1, memo)
    two_back = cheapest_memo(fee, i - 2, memo)
    memo[i] = fee[i] + min(one_back, two_back)
    return memo[i]


def cheapest_table(fee):
    global cells
    n = len(fee) - 1
    best = [0] * (n + 1)
    best[0] = fee[0]
    best[1] = fee[1]
    for i in range(2, n + 1):
        cells += 1
        cheaper = min(best[i - 1], best[i - 2])
        best[i] = fee[i] + cheaper
    return best[n]


for km in [10, 20, 30]:
    fee = fees(km)
    calls = 0
    cheapest(fee, km)
    plain = calls
    calls = 0
    cheapest_memo(fee, km, {})
    cells = 0
    cost = cheapest_table(fee)
    print(f"{km} км: {plain} / {calls} / {cells}, {cost} цента")

Изход

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

Пробвай

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

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

fee = fees(30)
memo = {}
cost = cheapest_memo(fee, 30, memo)
print(f"{cost} цента, {calls} извиквания")

Изход

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

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

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

1def cheapest_memo(fee, i, memo):2 if i <= 1:3 return fee[i]4 if i in memo:5 return memo[i]6 one_back = cheapest_memo(fee, i - 1, memo)7 two_back = cheapest_memo(fee, i - 2, memo)8 return fee[i] + min(one_back, two_back)

Провери

Пробвай

Попълни

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

def cheapest_table(fee):
    n = len(fee) - 1
    best = [0] * (n + 1)
    best[0] = fee[0]
    best[1] = fee[1]
    for i in range(2, n + 1):
        cheaper = min(best[i - 1], )
        best[i] = fee[i] + cheaper
    return best[n]

Провери

Упражнение

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

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

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

Вход

77 114 61 98 45 82

Изход

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

Още задачи

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

По-точно

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

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

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

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

def fees(n):
    return [0] + [40 + (i * 37) % 90 for i in range(1, n + 1)]


def cheapest_memo(fee, i, memo):
    if i <= 1:
        return fee[i]
    if i in memo:
        return memo[i]
    one_back = cheapest_memo(fee, i - 1, memo)
    two_back = cheapest_memo(fee, i - 2, memo)
    memo[i] = fee[i] + min(one_back, two_back)
    return memo[i]


def cheapest_table(fee):
    n = len(fee) - 1
    best = [0] * (n + 1)
    best[0] = fee[0]
    best[1] = fee[1]
    for i in range(2, n + 1):
        cheaper = min(best[i - 1], best[i - 2])
        best[i] = fee[i] + cheaper
    return best[n]


fee = fees(5000)
try:
    cheapest_memo(fee, 5000, {})
except RecursionError as e:
    print("cheapest_memo:", type(e).__name__)
print("cheapest_table:", cheapest_table(fee))

Изход

cheapest_memo: RecursionError
cheapest_table: 194418

Лимитът на Python е 1000 нива, затова пада още при 5000 км. Може да се вдигне със sys.setrecursionlimit, но за дълги маршрути таблицата е правилният избор.

Паметта, вградена в езика. В Python декораторът @functools.cache (от 3.9, а по-рано @functools.lru_cache(maxsize=None)) дава паметта наготово: пишеш наивната функция, слагаш декоратора над нея, и всеки отговор се пази по аргументите. Аргументите трябва да могат да са ключ в речник, затова списък с такси не става аргумент, а остава отвън.

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

Тест

Провери се

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