re:re:actable
Урок 033 минуты чтения

Что такое dynamic programming?

На этой странице
Кратко

Dynamic Programming, DP, - подход для задач с повторяющимися подзадачами и оптимальной подструктурой. Идея: решить каждую подзадачу один раз и переиспользовать результат.

Вопрос

Что такое dynamic programming и как определить состояние и переходы?

Когда нужен DP?

Два признака:

  1. Overlapping subproblems - одни и те же подзадачи повторяются.
  2. Optimal substructure - ответ строится из ответов меньших подзадач.

Пример: лестница

Условие (Climbing Stairs): лестница из n ступенек, за один шаг можно подняться на 1 или на 2 ступеньки. Сколько существует разных способов дойти до верха?

Для n = 4 способов 5:

1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2

Перебирать все варианты долго - их число растет экспоненциально. Заметим главное: на ступеньку i можно попасть только с i - 1 (шагом 1) или с i - 2 (шагом 2). Значит:

ways(i) = ways(i - 1) + ways(i - 2)

Это и есть DP: ответ для большой задачи складывается из ответов для меньших.

i12345
ways(i)121 + 2 = 32 + 3 = 53 + 5 = 8

Как решать DP-задачу по шагам

  1. State - что означает одна ячейка: dp[i] - число способов дойти до ступеньки i.
  2. Transition - как ячейка считается через предыдущие: dp[i] = dp[i - 1] + dp[i - 2].
  3. Base cases - что известно без вычислений: dp[1] = 1, dp[2] = 2.
  4. Порядок - от маленьких i к большим, чтобы нужные ячейки уже были посчитаны.
  5. Answer - где лежит итог: dp[n].

Top-down

Memoization:

function climbStairs(n: number, memo = new Map<number, number>()): number {
  if (n <= 2) return n
  if (memo.has(n)) return memo.get(n)!
 
  const ways = climbStairs(n - 1, memo) + climbStairs(n - 2, memo)
  memo.set(n, ways)
 
  return ways
}

Bottom-up

Tabulation:

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

Top-down и bottom-up дают одинаковый ответ и одинаковую сложность O(n). Top-down проще написать из рекурсивного решения, bottom-up не использует call stack.

Space optimization

dp[i] зависит только от двух предыдущих значений, поэтому весь массив хранить не нужно:

function climbStairs(n: number): number {
  if (n <= 2) return n
 
  let prev2 = 1
  let prev1 = 2
 
  for (let i = 3; i <= n; i++) {
    const current = prev1 + prev2
    prev2 = prev1
    prev1 = current
  }
 
  return prev1
}

Что отвечать на собеседовании?

DP применяют, когда задача состоит из повторяющихся подзадач, а ответ можно построить из меньших ответов. Есть top-down подход с memoization и bottom-up подход с таблицей. Сложность обычно считается как количество states умножить на стоимость transition.

Что важно помнить: частые ошибки

  • Применять DP там, где нет повторных подзадач.
  • Не определить state.
  • Не определить transition.
  • Не задать base cases.
  • Забыть порядок заполнения bottom-up.

Мини-шпаргалка

  • State - что храним.
  • Transition - как считаем.
  • Base cases - старт.
  • Answer - где лежит итог.
  • Top-down = memo.
  • Bottom-up = table.

Документация

Wikipedia: Dynamic programming.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам