2.4.2 — не структура, а свойство задачи: перекрывающиеся подзадачи плюс оптимальная подструктура2.4.2 — not a structure but a property of the problem: overlapping subproblems plus optimal substructure
В 2.4.1 каждая статья разбирала свою СТРУКТУРУ разбиения — умножение чисел, матриц, многочленов, точки на плоскости — и подзадачи в каждой были независимы: половины числа не пересекаются, левая оболочка не знает о правой. Здесь наоборот: каждая статья разбирает свою ЗАДАЧУ (рюкзак, наибольшая общая подпоследовательность, редакционное расстояние, коммивояжёр), но все они держатся на одном и том же механизме — рекурсия по подзадачам, которые повторяются экспоненциально много раз при наивном пересчёте, и which можно посчитать один раз и переиспользовать. Сам механизм — мемоизация и табуляция — разобран здесь, в общей части, а не вынесен в отдельную статью: это не отдельная структура, а фундамент, на котором строятся все шесть задач и последняя статья про оптимизацию перехода.In 2.4.1 every article covered its own splitting STRUCTURE — multiplying numbers, matrices, polynomials, points in the plane — and the subproblems in each were independent: a number's halves don't overlap, the left hull doesn't know about the right one. Here it's the opposite: every article covers its own PROBLEM (knapsack, longest common subsequence, edit distance, the traveling salesman), but all of them run on the same mechanism — recursion over subproblems that repeat exponentially many times under naive recomputation, and which can instead be computed once and reused. That mechanism itself — memoization and tabulation — is covered right here, in the shared section, rather than split out into its own article: it isn't a separate structure, it's the foundation all six problems and the final article on speeding up the transition are built on.
Задача поддаётся динамическому программированию, если у неё есть две черты одновременно. Первая — оптимальная подструктура: оптимальное решение всей задачи можно собрать из оптимальных решений её подзадач (для рюкзака — лучшее наполнение первых i предметов при вместимости w строится из лучшего наполнения первых i-1 предметов). Вторая — перекрывающиеся подзадачи: наивная рекурсия обращается к одним и тем же подзадачам многократно, и без переиспользования результата время растёт экспоненциально. Оба условия нужны сразу: у сортировки слиянием (2.2.1) есть оптимальная подструктура (отсортировать целое — значит слить две отсортированные половины), но подзадачи НЕ перекрываются (левая половина и правая — непересекающиеся куски массива), поэтому это разделяй-и-властвуй (2.4.1), а не ДП; кэшировать там нечего.A problem is amenable to dynamic programming if it has two traits at once. First, optimal substructure: the optimal solution to the whole problem can be assembled from optimal solutions to its subproblems (for knapsack, the best packing of the first i items at capacity w is built from the best packing of the first i-1 items). Second, overlapping subproblems: naive recursion revisits the same subproblems over and over, and without reusing the result, runtime grows exponentially. Both conditions are needed together: mergesort (2.2.1) has optimal substructure (sorting the whole thing means merging two sorted halves), but its subproblems do NOT overlap (the left half and the right half are disjoint chunks of the array), which is why it's divide-and-conquer (2.4.1), not DP — there's nothing to cache there.
Классическая иллюстрация "перекрывающихся подзадач" — числа Фибоначчи. fib(n) = fib(n-1) + fib(n-2) технически уже рекуррентное соотношение с оптимальной подструктурой (тривиальной — складывать нечего оптимизировать, но структура та же), но наивная рекурсия вызывает fib(n-2) дважды — один раз напрямую, один раз через fib(n-1) — и это удвоение накапливается на каждом уровне, давая дерево вызовов размером O(2^n) вместо O(n) узлов. Fibonacci слишком тривиален, чтобы заслуживать отдельной статьи (никакого нетривиального выбора при переходе нет — только одна формула), но это самый чистый пример механизма, вокруг которого построена вся тема: одна и та же подзадача fib(k) нужна много раз, и если её значение один раз посчитать и запомнить, дерево вызовов схлопывается в линейную цепочку.The classic illustration of "overlapping subproblems" is the Fibonacci numbers. fib(n) = fib(n-1) + fib(n-2) is technically already a recurrence with optimal substructure (a trivial one — there's no real choice to optimize, but the structure is the same), yet naive recursion calls fib(n-2) twice — once directly, once through fib(n-1) — and that doubling compounds at every level, producing a call tree of size O(2^n) instead of O(n) nodes. Fibonacci is too trivial to deserve its own article (there's no non-trivial choice at the transition — just one formula), but it's the cleanest possible example of the mechanism this whole topic is built around: the same subproblem fib(k) is needed many times, and computing its value once and remembering it collapses the call tree into a linear chain.
Есть ровно два эквивалентных способа это реализовать. Мемоизация (сверху вниз, top-down) — это обычная рекурсия плюс кэш: перед вычислением fib(k) проверяем, не считали ли мы его уже, и если да — возвращаем сохранённый результат вместо повторного спуска. Табуляция (снизу вверх, bottom-up) — это то же самое, но без рекурсии: заполняем таблицу dp[0], dp[1], ..., dp[n] итеративно в порядке возрастания, каждый раз используя уже готовые более ранние значения. Результат один и тот же — O(n) вместо O(2^n) — но табуляция обычно быстрее на практике (меньше константа: нет накладных расходов на вызов функции и нет риска переполнения стека вызовов на большой глубине рекурсии), тогда как мемоизация вычисляет только те подзадачи, которые реально понадобились (это может быть меньше полной таблицы, если не все состояния достижимы), и её код зачастую ближе по структуре к прямому переносу математической рекуррентности.There are exactly two equivalent ways to implement this. Memoization (top-down) is ordinary recursion plus a cache: before computing fib(k), check whether it's already been computed, and if so, return the stored result instead of descending again. Tabulation (bottom-up) does the same thing without recursion: fill a table dp[0], dp[1], ..., dp[n] iteratively in increasing order, each step using already-finished earlier values. The result is the same — O(n) instead of O(2^n) — but tabulation is usually faster in practice (smaller constant factor: no function-call overhead, and no risk of call-stack overflow at deep recursion), whereas memoization only computes the subproblems that were actually needed (which can be fewer than the full table, if not every state is reachable), and its code often mirrors the mathematical recurrence more directly.
это единственная роль Фибоначчи в теме 2.4.2 — иллюстрация механизма; у самой задачи нет отдельной статьи, потому что переход в ней тривиаленthis is Fibonacci's only role in topic 2.4.2 — illustrating the mechanism; the problem itself gets no article because its transition is trivial
Порядок — по возрастанию сложности состояния и перехода: сначала классическая 2D-таблица (рюкзак), затем 2D-таблица над двумя строками (LCS) и её прямое обобщение (редакционное расстояние), затем 1D-таблица с двумя разными скоростями решения одной и той же задачи (LIS), затем 1D-таблица с "неограниченным" использованием элементов (размен монет), затем принципиально другое представление состояния — множество как битовая маска (коммивояжёр), и в конце — не задача, а техника: как ускорить сам переход, когда рекуррентное соотношение уже написано.The order follows increasing state/transition complexity: first the classic 2D table (knapsack), then a 2D table over two strings (LCS) and its direct generalization (edit distance), then a 1D table with two different speeds for solving the same problem (LIS), then a 1D table with "unlimited" element reuse (coin change), then a fundamentally different state representation — a set encoded as a bitmask (the traveling salesman), and finally not a problem but a technique: how to speed up the transition itself once the recurrence is already written.
Первая карточка — рюкзак — вводит саму идею 2D-таблицы состояний "первые i элементов, ресурс w" и показывает, что рекуррентное соотношение здесь и есть весь алгоритм. Вторая и пятая карточки — LCS и редакционное расстояние — делят одну и ту же форму таблицы "первые i символов строки A, первые j символов строки B", различаясь только логикой перехода; понимание одной статьи напрямую переносится на другую. Третья карточка — единственная, где одна и та же задача решается дважды разными по духу способами: сначала прямая O(n²) ДП, затем ускорение через структуру данных (бинарный поиск), а не через изменение самой рекуррентности. Четвёртая карточка выглядит как рюкзак, но с одним критичным отличием — неограниченным использованием элементов, — которое меняет порядок обхода в пространственно-оптимизированной версии. Шестая карточка — качественный скачок: состояние индексируется не позицией, а множеством, и даже экспоненциальный 2^n·n² здесь — огромный прогресс по сравнению с n!. Седьмая карточка не вводит новую задачу вообще — она показывает, что после того как рекуррентность найдена, для некоторых задач можно ускорить сам цикл её вычисления.The first card — knapsack — introduces the idea of a 2D state table "first i elements, resource w" and shows that here the recurrence relation is the entire algorithm. The second and fifth cards — LCS and edit distance — share the exact same table shape "first i characters of string A, first j characters of string B," differing only in the transition logic; understanding one article carries directly over to the other. The third card is the only one where the same problem gets solved twice in fundamentally different spirits: first a direct O(n²) DP, then a speedup via a data structure (binary search) rather than by changing the recurrence itself. The fourth card looks like knapsack but with one critical difference — unlimited element reuse — which changes the iteration order in the space-optimized version. The sixth card is a qualitative leap: the state is indexed by a set, not a position, and even an exponential 2^n·n² is enormous progress compared to n!. The seventh card doesn't introduce a new problem at all — it shows that once a recurrence is found, for some problems the loop that computes it can itself be sped up.
Задачи "выбрать подмножество проектов/активов с ограниченным бюджетом, максимизируя ожидаемую отдачу" и составление расписания с ограниченными ресурсами (машинное время, число исполнителей) по сути являются вариациями рюкзака — 0/1, если каждый проект берётся целиком или не берётся, либо дробным/неограниченным, если делимость или повтор допустимы."Pick a subset of projects/assets under a limited budget to maximize expected return" and resource-constrained scheduling (machine time, headcount) are essentially knapsack variants — 0/1 if a project is taken whole or not at all, fractional or unbounded if divisibility or repetition is allowed.
Алгоритмы Нидлмана—Вунша (глобальное выравнивание) и Смита—Ватермана (локальное) — это прямые потомки редакционного расстояния (2.4.2.5) и LCS (2.4.2.2), где вместо букв алфавита сравниваются нуклеотиды или аминокислоты, а стоимости вставки/удаления/замены заменены на биологически осмысленные веса (матрицы замен вроде BLOSUM).The Needleman–Wunsch (global alignment) and Smith–Waterman (local alignment) algorithms are direct descendants of edit distance (2.4.2.5) and LCS (2.4.2.2), comparing nucleotides or amino acids instead of alphabet letters, with insert/delete/replace costs swapped for biologically meaningful weights (substitution matrices like BLOSUM).
Утилита Unix diff и построчный алгоритм сравнения, лежащий в основе git diff, по сути ищут наибольшую общую подпоследовательность строк между двумя версиями файла — неизменившиеся строки образуют LCS, а всё остальное помечается как добавленное или удалённое.The Unix diff utility and the line-matching algorithm underlying git diff are, at their core, searching for the longest common subsequence of lines between two file versions — unchanged lines form the LCS, and everything else is marked as added or removed.
Метод "терпеливой сортировки" (patience sorting), давший название O(n log n) варианту LIS (2.4.2.3), происходит из карточного пасьянса; та же идея — построение самой длинной возрастающей (или невозрастающей) цепочки — встречается в задачах вроде поиска максимальной цепочки вложенных интервалов или подбора совместимых по времени заданий, отсортированных по одному параметру.The "patience sorting" method, which gives its name to the O(n log n) LIS variant (2.4.2.3), originates from the card solitaire game; the same idea — building the longest increasing (or non-increasing) chain — shows up in problems like finding the longest chain of nested intervals or matching time-compatible tasks sorted by one parameter.
Точное решение задачи коммивояжёра через ДП по битовой маске (2.4.2.6, алгоритм Хелд—Карп) применимо, пока n (число точек доставки) остаётся малым — реалистично, до 15-20, потому что 2^n·n² быстро становится неподъёмным. Крупная логистика (сотни и тысячи точек) почти всегда использует эвристики и приближённые методы, а не точное ДП — честная оговорка, которую стоит проговорить сразу.The exact bitmask-DP solution to the traveling salesman problem (2.4.2.6, the Held–Karp algorithm) works as long as n (the number of delivery points) stays small — realistically up to 15-20, because 2^n·n² quickly becomes unmanageable. Large-scale logistics (hundreds or thousands of points) almost always relies on heuristics and approximation methods rather than exact DP — a caveat worth stating upfront.
Проверка орфографии ранжирует кандидатов на исправление по близости к введённому слову, где "близость" чаще всего измеряется именно редакционным расстоянием Левенштейна (2.4.2.5); системы автодополнения используют ту же метрику (или её ограниченные варианты вроде расстояния Дамерау—Левенштейна с перестановками соседних букв) для нечёткого поиска совпадений.Spell-checkers rank correction candidates by closeness to the typed word, where "closeness" is most often exactly the Levenshtein edit distance (2.4.2.5); autocomplete systems use the same metric (or bounded variants like Damerau–Levenshtein distance, which also allows adjacent-letter transpositions) for fuzzy matching.
В рюкзаке (2.4.2.1) каждый предмет берётся не более одного раза, в размене монет (2.4.2.4) каждый номинал можно использовать сколько угодно раз — с виду похожие одномерные рекуррентности после сжатия 2D-таблицы в 1D-массив требуют ПРОТИВОПОЛОЖНОГО порядка обхода по измерению "вместимость/сумма": для 0/1 рюкзака нужно идти по убыванию w (чтобы не использовать один и тот же предмет дважды в пределах одной итерации), для неограниченного варианта — по возрастанию (чтобы как раз разрешить повторное использование). Перепутанное направление цикла не упадёт с ошибкой — оно тихо посчитает не ту задачу.In knapsack (2.4.2.1) each item is taken at most once; in coin change (2.4.2.4) each denomination can be used any number of times — the outwardly similar 1D recurrences, after compressing the 2D table into a 1D array, need the OPPOSITE iteration direction over the "capacity/amount" dimension: for 0/1 knapsack you must iterate w in decreasing order (so the same item isn't used twice within one iteration), for the unbounded variant, in increasing order (to deliberately allow reuse). Getting the loop direction backwards won't crash — it will silently solve the wrong problem.
Оба подхода дают одну и ту же асимптотику, но не одну и ту же практическую скорость. Табуляция обычно быстрее по константе — нет накладных расходов на вызовы функций и нет риска переполнения стека вызовов при большой глубине рекурсии — но заполняет ВСЮ таблицу целиком, включая состояния, которые в реальности никогда не понадобились бы. Мемоизация считает только реально достижимые состояния (что может быть меньше полной таблицы), но платит за это накладными расходами рекурсии на каждый вызов. Для задач с сильно разреженным пространством состояний мемоизация может обогнать табуляцию по общему числу вычислений, несмотря на больший постоянный множитель на каждое вычисление.Both approaches give the same asymptotics but not the same practical speed. Tabulation is usually faster by a constant factor — no function-call overhead, no risk of call-stack overflow at deep recursion — but it fills in the ENTIRE table, including states that would never actually be needed. Memoization computes only the states that are actually reachable (which can be fewer than the full table), but pays recursion overhead on every call. For problems with a heavily sparse state space, memoization can outpace tabulation in total computation count, despite a larger constant factor per computation.
Convex Hull Trick требует, чтобы переход имел вид минимума по набору ЛИНЕЙНЫХ функций от точки запроса; D&C-оптимизация (2.4.2.7) требует, чтобы оптимальная точка перехода opt[i] была монотонна по i. Это не эвристики "обычно работает" — это точные предусловия. Если рекуррентность им не удовлетворяет, применение техники даёт не более медленный, а НЕПРАВИЛЬНЫЙ ответ, потому что алгоритм пропускает часть пространства поиска, считая, что она заведомо не может содержать оптимум. Обе техники — не универсальный ускоритель "давайте применим и на всякий случай проверим позже", а инструмент, применимый только после того, как структура задачи доказана или тщательно проверена на контрпримерах.The Convex Hull Trick requires the transition to take the form of a minimum over a set of LINEAR functions of the query point; D&C optimization (2.4.2.7) requires the optimal transition point opt[i] to be monotonic in i. These aren't "usually works" heuristics — they're exact preconditions. If the recurrence doesn't satisfy them, applying the technique doesn't just run slower — it gives a WRONG answer, because the algorithm skips part of the search space on the assumption that it provably can't contain the optimum. Neither technique is a universal speedup you apply and "check later just in case" — both are tools usable only after the problem's structure has been proven or carefully checked against counterexamples.