Как решать 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" (лишняя строка и столбец - пустой префикс):
"" | a | c | |
|---|---|---|---|
"" | 0 | 0 | 0 |
a | 0 | 1 | 1 |
b | 0 | 1 | 1 |
c | 0 | 1 | 2 |
В ячейке 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":
"" | c | u | t | |
|---|---|---|---|---|
"" | 0 | 1 | 2 | 3 |
c | 1 | 0 | 1 | 2 |
a | 2 | 1 | 1 | 2 |
t | 3 | 2 | 2 | 1 |
Ответ 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]
}Как думать?
- Что означает
dp[i][j]? - Какие base cases?
- От каких соседей зависит state?
- В каком порядке заполнять таблицу?
- Где лежит 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.