Динамическое программирование

Динамическое программирование простыми словами: почему наивная рекурсия считает одно и то же, как мемоизация и таблица убирают повтор, состояние и переход, разбор на примерах.

Опубликовано 24 августа 2026 обновлено 30 сентября 2026 ~18 мин чтения

← назад к разделу

Рекурсия сводит задачу к более простой версии самой себя. Иногда это работает прекрасно, а иногда программа намертво зависает на входе из сорока элементов. Почему так выходит и как это чинится — приём называется динамическим программированием.

Обязательно

Проблема: одно и то же считается многократно

Классический пример — числа Фибоначчи: каждое следующее равно сумме двух предыдущих.

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

func fib(n int) int64 {
	if n <= 1 {
		return int64(n)
	}
	return fib(n-1) + fib(n-2)
}

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

def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Код повторяет определение и совершенно нерабочий: fib(50) считается минутами. Причина видна на дереве вызовов: чтобы посчитать fib(5), нужны fib(4) и fib(3), но fib(4) внутри себя снова считает fib(3), а тот — снова fib(2). Число вызовов с каждым шагом растёт примерно в 1,6 раза. Кажется, немного, но рост степенной: на fib(50) вызовов набегает около сорока миллиардов.

Слева наивная рекурсия для fib(5): узел 3 разворачивается дважды, узел 2 — трижды, и глубже повторов только больше. Справа те же подзадачи в таблице: рамка проходит слева направо, и каждая ячейка считается один раз из двух соседей.

Ключевое наблюдение: подзадачи перекрываются. Их мало — всего n штук, — но наивная рекурсия не помнит, что уже считала.

Мемоизация: просто запомнить

Самое прямое лечение — завести блокнот и записывать туда посчитанное. Программа считает fib обоими способами и печатает, сколько вызовов ушло у каждого:

живой пример

import java.util.HashMap;
import java.util.Map;

public class FibCalls {
    static long naiveCalls, memoCalls;

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

    static long memo(int n, Map<Integer, Long> known) {
        memoCalls++;
        if (n <= 1) return n;
        Long ready = known.get(n);
        if (ready != null) return ready;
        long value = memo(n - 1, known) + memo(n - 2, known);
        known.put(n, value);
        return value;
    }

    public static void main(String[] args) {
        for (int n : new int[]{10, 20, 30}) {
            naiveCalls = memoCalls = 0;
            naive(n);
            memo(n, new HashMap<>());
            System.out.println("fib(" + n + "): наивно " + naiveCalls
                    + ", с блокнотом " + memoCalls);
        }
    }
}

Запустить

Запуск примеров доступен в платном доступе. Там этот же код выполняется прямо в статье: редактор, запуск и проверка рядом с абзацем. Три дня бесплатно →

живой пример

package main

import "fmt"

var naiveCalls, memoCalls int64

func naive(n int) int64 {
	naiveCalls++
	if n <= 1 {
		return int64(n)
	}
	return naive(n-1) + naive(n-2)
}

func memo(n int, known map[int]int64) int64 {
	memoCalls++
	if n <= 1 {
		return int64(n)
	}
	if ready, ok := known[n]; ok {
		return ready
	}
	value := memo(n-1, known) + memo(n-2, known)
	known[n] = value
	return value
}

func main() {
	for _, n := range []int{10, 20, 30} {
		naiveCalls, memoCalls = 0, 0
		naive(n)
		memo(n, map[int]int64{})
		fmt.Printf("fib(%d): наивно %d, с блокнотом %d\n", n, naiveCalls, memoCalls)
	}
}

Запустить

живой пример

let naiveCalls = 0;
let memoCalls = 0;

function naive(n) {
  naiveCalls++;
  if (n <= 1) return n;
  return naive(n - 1) + naive(n - 2);
}

function memo(n, known) {
  memoCalls++;
  if (n <= 1) return n;
  if (known.has(n)) return known.get(n);
  const value = memo(n - 1, known) + memo(n - 2, known);
  known.set(n, value);
  return value;
}

for (const n of [10, 20, 30]) {
  naiveCalls = memoCalls = 0;
  naive(n);
  memo(n, new Map());
  console.log(`fib(${n}): наивно ${naiveCalls}, с блокнотом ${memoCalls}`);
}

Запустить

В Python блокнот встроен в язык: декоратор functools.cache делает то же самое одной строкой над функцией. Ниже он выписан руками, чтобы посчитать вызовы:

живой пример

naive_calls = memo_calls = 0


def naive(n: int) -> int:
    global naive_calls
    naive_calls += 1
    if n <= 1:
        return n
    return naive(n - 1) + naive(n - 2)


def memo(n: int, known: dict[int, int]) -> int:
    global memo_calls
    memo_calls += 1
    if n <= 1:
        return n
    if n in known:
        return known[n]
    value = memo(n - 1, known) + memo(n - 2, known)
    known[n] = value
    return value


for n in (10, 20, 30):
    naive_calls = memo_calls = 0
    naive(n)
    memo(n, {})
    print(f"fib({n}): наивно {naive_calls}, с блокнотом {memo_calls}")

Запустить

Изменилось три строки, а сложность упала с экспоненциальной до O(n): каждое значение считается ровно один раз, дальше берётся из блокнота. На fib(30) это 59 вызовов вместо почти трёх миллионов. Такой подход называют «сверху вниз»: идём от большой задачи к маленьким, просто перестаём повторяться.

У блокнота есть предел. Хеш-таблица под ключ и значение стоит памяти и времени на хеширование, а сама рекурсия остаётся рекурсией: memo(100_000) упадёт с переполнением стека раньше, чем успеет что-то запомнить, потому что до базового случая сто тысяч вложенных вызовов; в Python предел и вовсе тысяча, а в Go стек дотянет, но тем же ходом съест мегабайты. Поэтому мемоизацию берут, когда состояний много, а посещаются немногие (блокнот заполняется лениво), а при глубокой цепочке зависимостей переходят к таблице из следующего раздела.

Таблица: снизу вверх

Если подзадачи можно упорядочить так, чтобы каждая опиралась только на уже посчитанные, рекурсия вообще не нужна — достаточно заполнить таблицу по порядку:

static long fib(int n) {
    if (n <= 1) return n;
    long[] dp = new long[n + 1];
    dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

func fib(n int) int64 {
	if n <= 1 {
		return int64(n)
	}
	dp := make([]int64, n+1)
	dp[1] = 1
	for i := 2; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[n]
}

function fib(n) {
  if (n <= 1) return n;
  const dp = new Array(n + 1).fill(0);
  dp[1] = 1;
  for (let i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
  return dp[n];
}

def fib(n: int) -> int:
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Это «снизу вверх». Работает быстрее (нет накладных расходов на вызовы) и не рискует переполнить стек. Плата — надо самому придумать порядок заполнения. Придумывается он механически, из той же рекурсии: посмотрите, к каким состояниям обращается переход, и заполняйте таблицу так, чтобы они были готовы раньше. fib(i) зовёт i − 1 и i − 2, значит заполняют по возрастанию i; рюкзак обращается к i − 1 и меньшему остатку, значит по возрастанию товаров, а внутри по остатку; если переход смотрит вправо (отрезки, где ответ зависит от концов), заполняют по возрастанию длины отрезка. Порядок заполнения это топологический порядок зависимостей между состояниями, и он читается из формулы перехода, а не придумывается.

Состояние и переход

К незнакомой задаче приём применяют, ответив на два вопроса.

Что такое состояние? Это набор параметров, полностью описывающий подзадачу. Для Фибоначчи состояние — одно число i. Для рюкзака — пара «сколько товаров рассмотрели» и «сколько места осталось».

Каков переход? Это формула, выражающая ответ для состояния через ответы для меньших. Плюс базовые случаи — состояния с готовым ответом.

Возьмём задачу: вдоль дороги стоят склады с выручкой, забирать с двух соседних подряд нельзя, нужна наибольшая сумма. Состояние — номер склада. Переход: склад либо пропускают (ответ такой же, как на предыдущем), либо берут — и тогда прибавляют к ответу двухшаговой давности, ведь соседний брать было нельзя.

живой пример

public class Pickup {
    public static void main(String[] args) {
        int[] revenue = {2, 7, 9, 3, 1, 8, 4};
        int skip = 0;
        int take = 0;
        for (int money : revenue) {
            int next = Math.max(skip, take);
            take = skip + money;
            skip = next;
        }
        System.out.println("наибольшая выручка: " + Math.max(skip, take));
    }
}

Запустить

живой пример

package main

import "fmt"

func main() {
	revenue := []int{2, 7, 9, 3, 1, 8, 4}
	skip, take := 0, 0
	for _, money := range revenue {
		next := max(skip, take)
		take = skip + money
		skip = next
	}
	fmt.Println("наибольшая выручка:", max(skip, take))
}

Запустить

живой пример

const revenue = [2, 7, 9, 3, 1, 8, 4];
let skip = 0;
let take = 0;
for (const money of revenue) {
  const next = Math.max(skip, take);
  take = skip + money;
  skip = next;
}
console.log("наибольшая выручка:", Math.max(skip, take));

Запустить

живой пример

revenue = [2, 7, 9, 3, 1, 8, 4]
skip = take = 0
for money in revenue:
    skip, take = max(skip, take), skip + money
print("наибольшая выручка:", max(skip, take))

Запустить

Здесь видна частая оптимизация: раз состояние зависит только от двух предыдущих, вся таблица сворачивается в две переменные — память O(1) вместо O(N).

Число это половина ответа: на практике нужно знать, какие именно склады дали максимум. Для этого во время заполнения запоминают, какой из двух вариантов победил в каждом состоянии, а в конце идут по этим пометкам с конца к началу.

живой пример

import java.util.ArrayDeque;
import java.util.Deque;

public class PickupRestore {
    public static void main(String[] args) {
        int[] revenue = {2, 7, 9, 3, 1, 8, 4};
        int n = revenue.length;
        int[] best = new int[n + 1];
        boolean[] taken = new boolean[n + 1];
        best[1] = revenue[0];
        taken[1] = true;
        for (int i = 2; i <= n; i++) {
            int take = best[i - 2] + revenue[i - 1];
            taken[i] = take > best[i - 1];
            best[i] = taken[i] ? take : best[i - 1];
        }
        Deque<Integer> chosen = new ArrayDeque<>();
        for (int i = n; i > 0; i = taken[i] ? i - 2 : i - 1) if (taken[i]) chosen.push(i);
        System.out.println("выручка " + best[n] + ", склады " + chosen);
    }
}

Запустить

живой пример

package main

import "fmt"

func main() {
	revenue := []int{2, 7, 9, 3, 1, 8, 4}
	n := len(revenue)
	best := make([]int, n+1)
	taken := make([]bool, n+1)
	best[1] = revenue[0]
	taken[1] = true
	for i := 2; i <= n; i++ {
		take := best[i-2] + revenue[i-1]
		taken[i] = take > best[i-1]
		if taken[i] {
			best[i] = take
		} else {
			best[i] = best[i-1]
		}
	}
	var chosen []int
	for i := n; i > 0; {
		if taken[i] {
			chosen = append([]int{i}, chosen...)
			i -= 2
		} else {
			i--
		}
	}
	fmt.Printf("выручка %d, склады %v\n", best[n], chosen)
}

Запустить

живой пример

const revenue = [2, 7, 9, 3, 1, 8, 4];
const n = revenue.length;
const best = new Array(n + 1).fill(0);
const taken = new Array(n + 1).fill(false);
best[1] = revenue[0];
taken[1] = true;
for (let i = 2; i <= n; i++) {
  const take = best[i - 2] + revenue[i - 1];
  taken[i] = take > best[i - 1];
  best[i] = taken[i] ? take : best[i - 1];
}
const chosen = [];
for (let i = n; i > 0; i = taken[i] ? i - 2 : i - 1) if (taken[i]) chosen.unshift(i);
console.log(`выручка ${best[n]}, склады [${chosen.join(", ")}]`);

Запустить

живой пример

revenue = [2, 7, 9, 3, 1, 8, 4]
n = len(revenue)
best = [0] * (n + 1)
taken = [False] * (n + 1)
best[1] = revenue[0]
taken[1] = True
for i in range(2, n + 1):
    take = best[i - 2] + revenue[i - 1]
    taken[i] = take > best[i - 1]
    best[i] = take if taken[i] else best[i - 1]
chosen = []
i = n
while i > 0:
    if taken[i]:
        chosen.insert(0, i)
        i -= 2
    else:
        i -= 1
print(f"выручка {best[n]}, склады {chosen}")

Запустить

Восстановление требует хранить таблицу целиком (свернуть её в две переменные уже нельзя) и массив решений, то есть память O(N) вместо O(1). В рюкзаке так же: идут от (n, capacity) назад и проверяют, отличается ли ячейка от ячейки без текущего товара; отличается, значит товар взяли.

Два измерения: рюкзак

Когда состояние описывается парой параметров, таблица становится двумерной. Классика — рюкзак: сумка выдерживает capacity килограммов, у товара есть вес и цена, кладут его целиком или не кладут.

Состояние — «рассмотрели первые i товаров, осталось left места», ответ — наибольшая цена. Переход: либо не берём товар (ответ как для i-1), либо берём (цена товара плюс ответ для i-1 с уменьшенным местом).

Таблицу тоже можно свернуть — до одной строки, но внутренний цикл обязан идти справа налево. Вот обе версии рядом:

живой пример

public class Knapsack {
    public static void main(String[] args) {
        int[] weights = {3, 4, 5};
        int[] prices = {40, 50, 60};
        int capacity = 10;
        int[] once = new int[capacity + 1];
        int[] many = new int[capacity + 1];
        for (int i = 0; i < weights.length; i++) {
            for (int left = capacity; left >= weights[i]; left--) {
                once[left] = Math.max(once[left], once[left - weights[i]] + prices[i]);
            }
            for (int left = weights[i]; left <= capacity; left++) {
                many[left] = Math.max(many[left], many[left - weights[i]] + prices[i]);
            }
        }
        System.out.println("справа налево: " + once[capacity]);
        System.out.println("слева направо: " + many[capacity]);
    }
}

Запустить

живой пример

package main

import "fmt"

func main() {
	weights := []int{3, 4, 5}
	prices := []int{40, 50, 60}
	capacity := 10
	once := make([]int, capacity+1)
	many := make([]int, capacity+1)
	for i := range weights {
		for left := capacity; left >= weights[i]; left-- {
			once[left] = max(once[left], once[left-weights[i]]+prices[i])
		}
		for left := weights[i]; left <= capacity; left++ {
			many[left] = max(many[left], many[left-weights[i]]+prices[i])
		}
	}
	fmt.Println("справа налево:", once[capacity])
	fmt.Println("слева направо:", many[capacity])
}

Запустить

живой пример

const weights = [3, 4, 5];
const prices = [40, 50, 60];
const capacity = 10;
const once = new Array(capacity + 1).fill(0);
const many = new Array(capacity + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
  for (let left = capacity; left >= weights[i]; left--) {
    once[left] = Math.max(once[left], once[left - weights[i]] + prices[i]);
  }
  for (let left = weights[i]; left <= capacity; left++) {
    many[left] = Math.max(many[left], many[left - weights[i]] + prices[i]);
  }
}
console.log("справа налево:", once[capacity]);
console.log("слева направо:", many[capacity]);

Запустить

живой пример

weights = [3, 4, 5]
prices = [40, 50, 60]
capacity = 10
once = [0] * (capacity + 1)
many = [0] * (capacity + 1)
for w, price in zip(weights, prices):
    for left in range(capacity, w - 1, -1):
        once[left] = max(once[left], once[left - w] + price)
    for left in range(w, capacity + 1):
        many[left] = max(many[left], many[left - w] + price)
print("справа налево:", once[capacity])
print("слева направо:", many[capacity])

Запустить

Ответы расходятся: при проходе слева направо ячейка left - weights[i] уже содержит результат с текущим товаром, и товар попадает в сумку несколько раз. Это уже другая задача — та, где предметы берут повторно.

Сложность — O(N · capacity). Выглядит полиномиальной, но это обманчиво: размер входа — не сама вместимость, а длина её записи. Миллиард — это десять цифр, и каждая новая цифра увеличивает работу в десять раз. На очень больших вместимостях приём перестаёт спасать.

Когда приём применим

Нужны два свойства одновременно:

перекрывающиеся подзадачи — наивная рекурсия решает одно и то же по многу раз; если подзадачи все разные, запоминать нечего;
оптимальная подструктура — ответ собирается из ответов для меньших подзадач; если оптимальный ответ требует неоптимального решения подзадачи, формула перехода неверна.

Признаки в условии: спрашивают количество способов или минимум и максимум по всем вариантам, а наивное решение — полный перебор «взять или не взять».

Если же на каждом шаге очевидно, что брать, и пересматривать это не приходится, хватит жадного прохода без таблицы.

Три исхода одного разбора: признак выбора стоит на стрелке, по нему и решают, нужна таблица, хватит жадного прохода или остаётся обычный перебор.

Дополнительно: при первом чтении можно пропустить

Глубже: расстояние Левенштейна: динамика по двум строкамрасширенное

Три примера выше про суммы, а самая применяемая в работе динамика про строки: сколько правок превращает одну строку в другую. На этом стоит diff в git, подсказка «возможно, вы имели в виду», сверка выгрузок с опечатками и нечёткий поиск по справочникам.

Состояние это пара «сколько символов первой строки разобрано, сколько второй», ответ для пары это минимум правок, чтобы превратить один префикс в другой. Переход: если последние символы совпали, правка не нужна и берут ответ для обоих префиксов без них; если нет, выбирают дешевейшее из трёх: заменить символ (ответ для обеих строк без последнего плюс один), удалить символ первой (без него плюс один), вставить символ второй (плюс один). Базовые случаи: пустую строку в строку длиной j превращают j вставками.

живой пример

public class Levenshtein {
    static int distance(String a, String b) {
        int[][] d = new int[a.length() + 1][b.length() + 1];
        for (int i = 0; i <= a.length(); i++) d[i][0] = i;
        for (int j = 0; j <= b.length(); j++) d[0][j] = j;
        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= b.length(); j++) {
                int same = a.charAt(i - 1) == b.charAt(j - 1) ? 0 : 1;
                d[i][j] = Math.min(d[i - 1][j - 1] + same, Math.min(d[i - 1][j] + 1, d[i][j - 1] + 1));
            }
        }
        return d[a.length()][b.length()];
    }

    public static void main(String[] args) {
        System.out.println(distance("кошка", "кот") + " " + distance("заказ", "показ") + " " + distance("abc", "abc"));
    }
}

Запустить

В Go строку сначала переводят в []rune: индексы по байтам на кириллице считали бы половинки символов.

живой пример

package main

import "fmt"

func distance(a, b string) int {
	ra, rb := []rune(a), []rune(b)
	d := make([][]int, len(ra)+1)
	for i := range d {
		d[i] = make([]int, len(rb)+1)
		d[i][0] = i
	}
	for j := range d[0] {
		d[0][j] = j
	}
	for i := 1; i <= len(ra); i++ {
		for j := 1; j <= len(rb); j++ {
			same := 1
			if ra[i-1] == rb[j-1] {
				same = 0
			}
			d[i][j] = min(d[i-1][j-1]+same, d[i-1][j]+1, d[i][j-1]+1)
		}
	}
	return d[len(ra)][len(rb)]
}

func main() {
	fmt.Println(distance("кошка", "кот"), distance("заказ", "показ"), distance("abc", "abc"))
}

Запустить

живой пример

function distance(a, b) {
  const d = Array.from({ length: a.length + 1 }, (_, i) => {
    const row = new Array(b.length + 1).fill(0);
    row[0] = i;
    return row;
  });
  for (let j = 0; j <= b.length; j++) d[0][j] = j;
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      const same = a[i - 1] === b[j - 1] ? 0 : 1;
      d[i][j] = Math.min(d[i - 1][j - 1] + same, d[i - 1][j] + 1, d[i][j - 1] + 1);
    }
  }
  return d[a.length][b.length];
}

console.log(distance("кошка", "кот"), distance("заказ", "показ"), distance("abc", "abc"));

Запустить

живой пример

def distance(a: str, b: str) -> int:
    d = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(len(a) + 1):
        d[i][0] = i
    for j in range(len(b) + 1):
        d[0][j] = j
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            same = 0 if a[i - 1] == b[j - 1] else 1
            d[i][j] = min(d[i - 1][j - 1] + same, d[i - 1][j] + 1, d[i][j - 1] + 1)
    return d[len(a)][len(b)]


print(distance("кошка", "кот"), distance("заказ", "показ"), distance("abc", "abc"))

Запустить

O(N·M) по времени и памяти, а память сворачивается до двух строк таблицы, как и в рюкзаке. Наибольшая общая подпоследовательность (сколько символов можно оставить, чтобы строки совпали) считается той же таблицей с переходом «совпали: диагональ плюс один, нет: максимум слева и сверху», и именно её строит diff, помечая всё остальное как удалённое и добавленное.

Глубже: жадный алгоритм: когда он даёт оптимум, а когда врётрасширенное

Слово «жадно» встречалось у Прима, здесь и в выборе структуры: на каждом шаге берём то, что лучше всего прямо сейчас, и никогда не пересматриваем. Это самый быстрый способ решать оптимизационные задачи и самый опасный: жадность даёт оптимум только там, где локально лучший шаг не портит будущее.

Пример, где даёт. Выбор максимального числа непересекающихся встреч: сортируем по времени окончания и каждый раз берём ту, что заканчивается раньше всех и не пересекается с уже взятой. Взять кончающуюся раньше всегда не хуже любого другого выбора: она оставляет больше времени остальным. Так же устроены размен монетами номиналов 1, 5, 10, 50 и код Хаффмана.

Пример, где врёт. Те же монеты, но номиналы 1, 3, 4: сумму 6 жадность собирает как 4 + 1 + 1, три монеты, а оптимум 3 + 3. Рюкзак с неделимыми предметами: взять самый ценный за килограмм не значит набрать самый ценный рюкзак. Здесь ранний выбор закрывает лучшую комбинацию, и нужна динамика: она честно перебирает состояния и сравнивает.

Как понять, какая задача перед вами. У жадности два признака применимости: можно доказать, что локально лучший выбор входит в какое-то оптимальное решение (любое оптимальное решение перестраивается так, чтобы начинаться с жадного шага, не ухудшаясь), и что задача после этого шага остаётся той же задачей меньшего размера. Если доказать не выходит, ищут контрпример на маленьком входе, как с монетами 1, 3, 4. Нашли, значит динамическое программирование; не нашли и обмен работает, значит жадность, и решение будет на порядок быстрее.

Коротко

Динамическое программирование — это перебор, который не повторяет уже сделанную работу.
Условие применимости: подзадачи перекрываются, а ответ собирается из ответов на меньшие подзадачи.
Мемоизация («сверху вниз») — рекурсия плюс блокнот: три новые строки, и вместо миллионов вызовов остаётся по одному расчёту на состояние. Для Фибоначчи это 2n−1 вызовов; у другой задачи число своё — оно зависит от того, сколько состояний и сколько вызовов делает каждое.
Таблица («снизу вверх») — заполнение по порядку без рекурсии: быстрее и без риска переполнить стек вызовов.
Проектирование сводится к двум вопросам: что такое состояние и каков переход между состояниями.
В свёрнутой таблице направление внутреннего цикла определяет, можно ли брать предмет повторно, а память падает до O(1).
Жадность берут, когда локально лучший шаг доказуемо входит в оптимум (встречи по времени окончания); монеты 1, 3, 4 на сумме 6 показывают, где она врёт и нужна динамика.
Блокнот не спасает от глубокой рекурсии (переполнение стека вызовов) и стоит памяти; порядок заполнения таблицы читается из перехода: то, к чему он обращается, заполняют раньше.
Сам ответ восстанавливают по пометкам «какой вариант победил», идя с конца; таблицу при этом хранят целиком.
Расстояние Левенштейна: таблица по двум строкам, переход из трёх правок, O(N·M); та же таблица даёт наибольшую общую подпоследовательность, на которой стоит diff.

Что почитать дальше

Рекурсия — откуда берётся дерево вызовов.
Математика для O-нотации — почему рост в 1,6 раза за шаг убивает программу, а O(n) нет.
Префиксные суммы — тот же принцип «посчитать один раз и запомнить» в простейшем виде.
Перебор с отсечением — когда нужны сами варианты, а не их количество или максимум.