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

Как решать DP по строкам и таблицам?

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

DP по строкам и таблицам часто строится на двумерном состоянии dp[i][j]: префикс первой строки и префикс второй строки, или клетка i,j в grid. Классика: LCS, edit distance, unique paths.

Вопрос

Как решать DP-задачи по строкам и таблицам: LCS, edit distance, пути в сетке?

Longest Common Subsequence

Subsequence (подпоследовательность) - символы строки в том же порядке, но не обязательно подряд. Для "abcde" подпоследовательности - "ace", "bd", "abe", но не "ca". LCS - самая длинная подпоследовательность, общая для двух строк: для "abcde" и "ace" это "ace", длина 3.

State:

dp[i][j] = LCS длина для text1[0..i) и text2[0..j)
function longestCommonSubsequence(a: string, b: string): number {
  const dp = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0))
 
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
      }
    }
  }
 
  return dp[a.length][b.length]
}

Логика перехода:

  • последние символы совпали - они входят в общую подпоследовательность: берем ответ без них и прибавляем 1;
  • не совпали - один из них лишний: пробуем выбросить последний символ a или последний символ b и берем лучшее.

Таблица для a = "abc", b = "ac" (лишняя строка и столбец - пустой префикс):

""ac
""000
a011
b011
c012

В ячейке c / c символы совпали: берем значение по диагонали (1) и прибавляем 1. Ответ в правом нижнем углу - 2 ("ac").

Edit distance

Минимальное число операций (вставить, удалить, заменить символ), чтобы превратить строку a в строку b. Так работают подсказки "возможно, вы имели в виду...".

State:

dp[i][j] = сколько операций нужно, чтобы превратить a[0..i) в b[0..j)
function editDistance(a: string, b: string): number {
  const dp = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0))
 
  for (let i = 0; i <= a.length; i++) dp[i][0] = i // удалить все i символов
  for (let j = 0; j <= b.length; j++) dp[0][j] = j // вставить все j символов
 
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] // символы совпали, операция не нужна
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j], // удалить символ из a
          dp[i][j - 1], // вставить символ из b
          dp[i - 1][j - 1], // заменить символ
        )
      }
    }
  }
 
  return dp[a.length][b.length]
}

Таблица для "cat" -> "cut":

""cut
""0123
c1012
a2112
t3221

Ответ 1: заменить a на u. Для "horse" -> "ros" ответ 3.

Grid DP

Unique paths: робот стоит в левом верхнем углу сетки и ходит только вправо или вниз. Сколько разных путей до правого нижнего угла?

В клетку можно прийти только сверху или слева, поэтому dp[r][c] = dp[r - 1][c] + dp[r][c - 1]. В первую строку и первый столбец ведет ровно один путь, поэтому таблица заполнена единицами.

сетка 3 x 3:
1  1  1
1  2  3
1  3  6    <- 6 путей
function uniquePaths(rows: number, cols: number): number {
  const dp = Array.from({ length: rows }, () => new Array(cols).fill(1))
 
  for (let r = 1; r < rows; r++) {
    for (let c = 1; c < cols; c++) {
      dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
    }
  }
 
  return dp[rows - 1][cols - 1]
}

Как думать?

  1. Что означает dp[i][j]?
  2. Какие base cases?
  3. От каких соседей зависит state?
  4. В каком порядке заполнять таблицу?
  5. Где лежит answer?

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

В строковых и grid DP часто используется двумерная таблица. Для строк dp[i][j] обычно означает ответ на префиксах двух строк. Для grid dp[r][c] означает лучший/количество способов дойти до клетки. Важно четко определить state, transition, base cases и порядок заполнения.

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

  • Не добавлять extra row/column для пустого префикса.
  • Путать i и i - 1 в строке.
  • Заполнять таблицу в неправильном порядке.
  • Не понимать, что именно хранит dp[i][j].
  • Сразу оптимизировать память до понимания 2D решения.

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

  • Strings -> prefixes.
  • Grid -> cells.
  • dp[i][j] должен иметь смысл.
  • Base row/column часто нули или единицы.
  • Transition from neighbors.
  • Answer usually bottom-right.

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

Wikipedia: Longest common subsequence, Wikipedia: Levenshtein distance.

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

Поиск

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