Алгоритмы с нуля

Одномерная ДП: грабитель домов, подъём по лестнице, способы декодирования

Суть Шаблон одномерной ДП: состояние — одна позиция i, dp[i] зависит от нескольких более ранних ячеек. House Robber: max(dp[i-1], dp[i-2]+nums[i]); Climbing Stairs — это Фибоначчи; Decode Ways считает декодирования строки цифр. O(n) время, O(1) память.

◷ 28 min

Теперь ты знаешь два способа запустить ДП: мемоизацию сверху вниз и табуляцию снизу вверх. Но оба это просто движки. Настоящий навык это прочитать совсем новую задачу и увидеть ДП спрятанную внутри неё: что это состояние, и как один ответ строится на ответах до него? Этот урок отрабатывает самую частую форму из всех — одномерную ДП, где состояние это одна позиция i в последовательности, а dp[i] определяется всего парой более ранних ячеек. Три классические задачи, все один скелет: House Robber (грабитель домов), Climbing Stairs (подъём по лестнице) и Decode Ways (способы декодирования). Научись замечать эту форму, и огромный пласт “сложных” задач с собеседований сворачивается в однострочную рекурренту и цикл.

Цель

После этого урока ты можешь распознавать и решать задачи одномерного динамического программирования. Ты можешь выполнить четырёхшаговую процедуру для любой из них: (1) определи состояние — что значит dp[i] одним точным предложением; (2) запиши рекурренту что связывает dp[i] с несколькими более ранними ячейками; (3) задай базовые случаи; (4) назови ячейку-ответ. Ты можешь применить её к трём классикам: House Robber (dp[i] = max(dp[i-1], dp[i-2] + nums[i]), никогда не грабь соседние дома), Climbing Stairs (dp[i] = dp[i-1] + dp[i-2] — это Фибоначчи) и Decode Ways (посчитай декодирования строки цифр, обрабатывая крайние случаи с '0'). Ты можешь сжать каждую из O(n) массива до O(1) памяти используя скользящие переменные, потому что рекуррента смотрит назад только на фиксированное расстояние. Следующий урок переходит к двумерной ДП, где состояние это пара (i, j).

Идея

Что значит “одномерная ДП”

Одномерная ДП это динамическая программа чьё состояние это один индекс i — обычно позиция в массиве или строке. Ты строишь массив dp где dp[i] это ответ на подзадачу заканчивающуюся в (или использующую) позиции i, а рекуррента выражает dp[i] используя только фиксированное число более ранних ячеек (почти всегда dp[i-1] и dp[i-2]). Это свойство “смотрит назад только на константное расстояние” это ровно то, что позже позволяет тебе отбросить весь массив и держать всего несколько переменных.

Четырёхшаговая процедура

Каждая задача ниже решается тем же чек-листом. Запомни вопросы, не ответы:

Состояние. Закончи это предложение точно: “dp[i] это …”. Расплывчатое состояние это причина №1 неправильных ДП.
Рекуррента. Как dp[i] строится из более ранних ячеек? Это единственная творческая строка.
Базовые случаи. Наименьшие входы которых рекуррента не может достичь (dp[0], иногда dp[1]).
Ячейка-ответ. Какая запись хранит итоговый результат — обычно dp[n-1] или dp[n].

Задача 1 — House Robber (грабитель домов)

Ты грабитель на улице домов, nums[i] наличных в доме i. Грабёж двух соседних домов включает сигнализацию. Максимизируй добычу.

Состояние: dp[i] = максимум что ты можешь награбить рассматривая дома 0..i.
Рекуррента: в доме i ты либо пропускаешь его (держишь dp[i-1]), либо грабишь его (берёшь nums[i] плюс лучшее с двух назад, dp[i-2], потому что i-1 теперь под запретом): dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
Базовые случаи: dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]).
Ответ: dp[n-1].

Смотри как заполняется таблица для nums = [2, 7, 9, 3, 1]. Каждая ячейка это лучшее из “пропустить” (ячейка слева) и “ограбить” (ячейка на две слева плюс этот дом):

index     i=0   i=1   i=2    i=3    i=4
nums       2     7     9      3      1
                |     |      |      |
skip  dp[i-1]:  -     2      7     11     11
rob   dp[i-2]+n:-    (-+7)  (2+9) (7+3) (11+1)
                            = 11  = 10   = 12
                |     |      |      |
dp:        2     7    11     11     12   <- answer = 12

Жадное “всегда хватай самый богатый дом” провалилось бы; ДП взвешивает каждый выбор пропустить-против-ограбить используя ответы которые она уже посчитала.

Задача 2 — Climbing Stairs (подъём по лестнице) (это Фибоначчи)

Ты поднимаешься по лестнице из n ступеней, делая 1 или 2 шага за раз. Сколько различных способов достичь верха?

Состояние: dp[i] = число различных способов достичь ступени i.
Рекуррента: последний ход приземлился на ступень i либо со ступени i-1 (шаг на 1), либо со ступени i-2 (шаг на 2), так что dp[i] = dp[i-1] + dp[i-2]. Это правило Фибоначчи.
Базовые случаи: dp[0] = 1 (один способ “стоять внизу” — ничего не делать); dp[1] = 1 (единственный шаг на 1).
Ответ: dp[n].

step i:   0   1   2   3   4   5
ways:     1   1   2   3   5   8   <- climb(5) = 8
                  ^   ^
            2=1+1   3=2+1  (each = sum of the two before it)

Задача 3 — Decode Ways (способы декодирования)

A=1, B=2, ..., Z=26. Дана строка цифр вроде "226", посчитай сколькими способами она декодируется ("226" → "BBF", "BZ", "VF" = 3). Подвох это нули и диапазон 1–26.

Состояние: dp[i] = число способов декодировать первые i символов строки. (Заметь сдвиг на единицу: dp индексируется обработанной длиной, не позицией символа, так что dp имеет n+1 ячеек.)
Рекуррента: посмотри на последние один или два символа перед длиной i.
- Если одиночная цифра s[i-1] это '1'–'9' (не '0'), она образует валидную букву сама по себе → прибавь dp[i-1].
- Если две цифры s[i-2..i-1] образуют число 10–26, они образуют валидную букву вместе → прибавь dp[i-2].
- dp[i] = (s[i-1] != '0' ? dp[i-1] : 0) + (10 <= twoDigit <= 26 ? dp[i-2] : 0).
Базовые случаи: dp[0] = 1 (один способ декодировать пустой префикс); dp[1] = 1 если s[0] не '0', иначе 0 (ведущий ноль не декодирует ничего).
Ответ: dp[n].

Ноль это то, что делает это сложным. '0' никогда не буква сам по себе (нет буквы 0), так что одинокий '0' ничего не вносит, и только "10" и "20" когда-либо потребляют '0' валидно (как J и T). Что-то вроде "30", "06" или хвостовой "...0" без валидного двузначного партнёра означает ноль всего декодирований — весь счёт сворачивается в 0.

"226":  dp[0]=1  dp[1]=1  dp[2]=2  dp[3]=3
"06" :  s[0]='0' -> dp[1]=0 -> answer 0   (leading zero, dead)
"100":  ...the final '0' has no valid 2-digit partner ("00") -> 0

Код

House Robber, учебная одномерная ДП

Вот House Robber с явным массивом dp чтобы рекуррента была видна, потом мы её сворачиваем.


      1
      function rob(nums) {
    

      2
      const n = nums.length;
    

      3
      if (n === 0) return 0;
    

      4
      if (n === 1) return nums[0];
    

      5
       
    

      6
      const dp = new Array(n);
    

      7
      dp[0] = nums[0];                       // base: only house 0
    

      8
      dp[1] = Math.max(nums[0], nums[1]);    // base: best of the first two
    

      9
       
    

      10
      for (let i = 2; i < n; i++) {
    

      11
        // skip house i  -> dp[i-1]
    

      12
        // rob  house i  -> dp[i-2] + nums[i]  (i-1 is now forbidden)
    

      13
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    

      14
      }
    

      15
       
    

      16
      return dp[n - 1];                      // answer cell
    

      17
      }

L3 Крайний случай: нет домов значит нет добычи.
L4 Крайний случай: единственный дом грабится сразу.
L7 Базовый случай dp[0]: единственный вариант это ограбить дом 0.
L8 Базовый случай dp[1]: ограбь тот из первых двух домов где больше.
L13 Рекуррента: лучшее из пропуска дома i (dp[i-1]) против его грабежа (dp[i-2] + nums[i]).
L16 Ответ это последняя ячейка: лучшая добыча по всем домам.

Сворачивание до O(1) памяти

dp[i] только читает dp[i-1] и dp[i-2]. Так что нам никогда не нужен весь массив — двух скользящих переменных достаточно. Тот же приём работает для всех трёх задач, потому что каждая рекуррента смотрит назад на фиксированное расстояние.

prev2 = dp[i-2]   prev1 = dp[i-1]
cur = recurrence(prev1, prev2)
then slide: prev2 = prev1, prev1 = cur

Запуск всех трёх (скользящие, O(1) память)

// House Robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
function rob(nums) {
let prev2 = 0;            // best up to i-2
let prev1 = 0;            // best up to i-1
for (const x of nums) {
  const take = prev2 + x; // rob this house
  const skip = prev1;     // skip this house
  const cur = Math.max(skip, take);
  prev2 = prev1;
  prev1 = cur;
}
return prev1;
}

// Climbing Stairs: dp[i] = dp[i-1] + dp[i-2]  (Fibonacci)
function climbStairs(n) {
let prev2 = 1;            // ways to reach step 0
let prev1 = 1;            // ways to reach step 1
for (let i = 2; i <= n; i++) {
  const cur = prev1 + prev2;
  prev2 = prev1;
  prev1 = cur;
}
return prev1;
}

// Decode Ways: 1-digit and valid 2-digit predecessors, zeros are deadly
function numDecodings(s) {
if (s.length === 0 || s[0] === "0") return 0;
let prev2 = 1;            // dp[0]: empty prefix
let prev1 = 1;            // dp[1]: first char is non-zero here
for (let i = 2; i <= s.length; i++) {
  let cur = 0;
  if (s[i - 1] !== "0") cur += prev1;          // single digit 1..9
  const two = Number(s.slice(i - 2, i));       // last two digits
  if (two >= 10 && two <= 26) cur += prev2;    // valid pair 10..26
  prev2 = prev1;
  prev1 = cur;
}
return prev1;
}

console.log("House Robber:");
console.log("  [2,7,9,3,1] ->", rob([2, 7, 9, 3, 1]));
console.log("  [1,2,3,1]   ->", rob([1, 2, 3, 1]));
console.log("Climbing Stairs:");
console.log("  n=5  ->", climbStairs(5));
console.log("  n=10 ->", climbStairs(10));
console.log("Decode Ways:");
console.log("  '226' ->", numDecodings("226"));
console.log("  '06'  ->", numDecodings("06"));
console.log("  '100' ->", numDecodings("100"));

Вывод

'06' возвращает 0 (ведущий ноль), а '100' возвращает 0 (последний '0' не имеет валидного двузначного партнёра) — крайние случаи с нулём которые рекуррента должна соблюдать.

Пошаговый разбор

Заполним таблицу House Robber для nums = [2, 7, 9, 3, 1] ячейка за ячейкой. Каждое dp[i] это лучшее из пропустить (dp[i-1]) и ограбить (dp[i-2] + nums[i]).


      1
      dp[0] = nums[0];
    

      2
      dp[1] = max(nums[0], nums[1]);
    

      3
      for (let i = 2; i < n; i++)
    

      4
        dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
    

      5
      return dp[n-1];

Сложность

Время: O(n)

Все три задачи делают один проход по входу длины n, и каждая ячейка стоит O(1) работы (один max, или одно-два сложения, или пара проверок цифр). Так что время это число состояний умноженное на работу на состояние: n состояний x O(1) = O(n).

problem           states   work/state   time
House Robber      n        O(1)         O(n)
Climbing Stairs   n+1      O(1)         O(n)
Decode Ways       n+1      O(1)         O(n)

Память: O(n) с массивом, O(1) со скользящими переменными

Наивная таблица хранит каждое dp[i]: O(n) памяти. Но каждая рекуррента здесь смотрит назад только на фиксированное расстояние — dp[i-1] и dp[i-2] — так что тебе нужны только последние два значения. Замени массив двумя переменными (prev1, prev2) и сдвигай их вперёд каждый шаг:

                  array      rolling
House Robber      O(n)       O(1)
Climbing Stairs   O(n)       O(1)
Decode Ways       O(n)       O(1)

Правило что разрешает O(1) память: если dp[i] зависит только от последних k ячеек, тебе нужно только k переменных, не весь массив. Здесь k = 2 для всех трёх. Это фирменная оптимизация одномерной ДП, и вот почему интервьюеры любят эти задачи — они хотят увидеть как ты замечаешь ограниченный взгляд назад и отбрасываешь массив.

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

Практика 0 / 8

Какая рекуррента House Robber (нельзя грабить два соседних дома)?

Почему Climbing Stairs это то же что Фибоначчи?

В Decode Ways, что представляет состояние dp[i]?

Сколькими способами строка '226' может быть декодирована (A=1..Z=26)?

Почему строка '06' декодируется 0 способами?

Почему House Robber, Climbing Stairs и Decode Ways все могут работать за O(1) памяти?

Для House Robber с nums = [2, 7, 9, 3, 1], какая максимальная добыча (ячейка-ответ dp[4])?

Climbing Stairs с n = 5: сколько различных способов достичь верха (1 или 2 шага за раз)?

Почему это работает

Почему “определи состояние одним точным предложением” так важно. Большинство неправильных ДП не неправильные рекурренты — они расплывчатые состояния. “dp[i] это ответ пока что” не значит ничего против чего ты можешь написать рекурренту. Сравни три чётких определения здесь: dp[i] у House Robber это “максимум что ты можешь награбить рассматривая дома 0..i”; dp[i] у Decode Ways это “число способов декодировать первые i символов.” Как только предложение точное, рекуррента обычно пишется сама, потому что ты можешь спросить “при этом определении, как ячейка i зависит от более ранних ячеек?” и ответ вынужден. Трать время на размышления о состоянии, не о коде.

Граничные случаи

Нули в Decode Ways. Это крайний случай что ломает наивные решения. Три вещи которые надо сделать правильно: (1) Ведущий ‘0’ (s[0] === '0') означает что вся строка декодируется 0 способами — выходи немедленно. (2) Одинокий ‘0’ никогда не буква, так что ветка одной цифры должна проверять s[i-1] !== '0' перед прибавлением dp[i-1]. (3) ‘0’ валиден только как вторая цифра “10” или “20”; “30”..“90” и “00” это невалидные пары, так что ‘0’ без валидного партнёра (вроде хвостового ‘0’ в “100”, или “06”, или “30”) вынуждает dp[i]=0 и счёт умирает. Протестируй свой код на “10” (=1, валидно как J), “100” (=0), “2101” (=1) и “06” (=0).

Частая ошибка

Забывание что Decode Ways индексируется длиной, не позицией. Соблазнительно сделать dp[i] значащим “декодирования заканчивающиеся ровно на символе i,” но чистая версия индексирует dp числом потреблённых символов: dp[i] = способы декодировать первые i символов. Это даёт dp.length = n+1, базовый случай пустого префикса dp[0]=1 и ответ dp[n]. Смешивание двух конвенций это классический сдвиг на единицу что производит правильно-выглядящие-но-неправильные счёты. Выбери конвенцию длины и базовые случаи выстраиваются чисто.

Ещё практика

Четырёхшаговая процедура на свежей задаче. Попробуй “Min Cost Climbing Stairs”: каждая ступень i имеет стоимость cost[i]; ты можешь начать со ступени 0 или 1, подниматься на 1 или 2 за раз, платить стоимость каждой ступени на которой стоишь, и достичь за вершину. (1) Состояние: dp[i] = минимальная стоимость достичь ступени i. (2) Рекуррента: dp[i] = cost[i] + min(dp[i-1], dp[i-2]). (3) База: dp[0] = cost[0], dp[1] = cost[1]. (4) Ответ: min(dp[n-1], dp[n-2]) (ты можешь шагнуть за вершину с любой из последних двух). Тот же скелет, новая рекуррента — это весь шаблон. Потом сверни его до O(1) памяти двумя скользящими переменными.

Проверь себя

Викторина

Объясни шаблон одномерной ДП: что это состояние, как работают рекурренты трёх задач, крайние случаи с нулём в Decode Ways, и почему O(1) память возможна.

Итог

Одномерная ДП имеет одноиндексное состояние: dp[i] отвечает на подзадачу на позиции i, а рекуррента читает только фиксированное число более ранних ячеек. Реши любую из них четырьмя шагами: определи состояние точно, запиши рекурренту, задай базовые случаи, назови ячейку-ответ.

Три классики:

House Robber — dp[i] = max(dp[i-1], dp[i-2] + nums[i]); пропуск против грабежа, никогда не два соседних. Ответ dp[n-1].
Climbing Stairs — dp[i] = dp[i-1] + dp[i-2]; это Фибоначчи, считающее способы по последнему (1- или 2-) шагу. Ответ dp[n].
Decode Ways — dp[i] = способы декодировать первые i символов; прибавь dp[i-1] когда одиночная цифра ненулевая и dp[i-2] когда последние две цифры это 10–26. Ведущий '0' или непарный '0' (вроде '06', '100', '30') роняет счёт до 0.

Сложность: O(n) время для всех трёх. O(1) память со скользящими переменными, потому что каждая рекуррента смотрит назад только на две ячейки — фирменная оптимизация одномерной ДП. (Держи весь массив только если ты должен восстановить фактические выборы.)

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

Продолжить восхождение ↑Двумерная ДП: пути в сетке, LCS, расстояние редактирования