Hard💻Практика8 min

DP на строках

Longest Common Subsequence, Edit Distance, Palindrome задачи

AlgoDynamic programming

DP на строках

Задача 1: Longest Common Subsequence (LCS)

Условие: найти длину наибольшей общей подпоследовательности двух строк.

s1 = "abcde"
s2 = "ace"
LCS = "ace", длина 3

Рекуррентность

Если s1[i-1] == s2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1      # Символы совпали
Иначе:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # Пропускаем один из символов
PHPGo
<?php
declare(strict_types=1);

function longestCommonSubsequence(string $s1, string $s2): int
{
    $m = strlen($s1);
    $n = strlen($s2);
    $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));

    for ($i = 1; $i <= $m; $i++) {
        for ($j = 1; $j <= $n; $j++) {
            if ($s1[$i - 1] === $s2[$j - 1]) {
                $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
            } else {
                $dp[$i][$j] = max($dp[$i - 1][$j], $dp[$i][$j - 1]);
            }
        }
    }

    return $dp[$m][$n];
}

package main

func longestCommonSubsequence(s1, s2 string) int {
    m, n := len(s1), len(s2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if s1[i-1] == s2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }

    return dp[m][n]
}
Визуализация таблицы для "abcde" и "ace": 
      ""  a  c  e
  ""   0  0  0  0
  a    0  1  1  1
  b    0  1  1  1
  c    0  1  2  2
  d    0  1  2  2
  e    0  1  2  3  <- ответ

Восстановление LCS

PHPGo
<?php
declare(strict_types=1);

function getLcs(string $s1, string $s2): string
{
    $m = strlen($s1);
    $n = strlen($s2);
    $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));

    for ($i = 1; $i <= $m; $i++) {
        for ($j = 1; $j <= $n; $j++) {
            if ($s1[$i - 1] === $s2[$j - 1]) {
                $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
            } else {
                $dp[$i][$j] = max($dp[$i - 1][$j], $dp[$i][$j - 1]);
            }
        }
    }

    // Reconstruct LCS
    $lcs = '';
    $i = $m;
    $j = $n;
    while ($i > 0 && $j > 0) {
        if ($s1[$i - 1] === $s2[$j - 1]) {
            $lcs = $s1[$i - 1] . $lcs;
            $i--;
            $j--;
        } elseif ($dp[$i - 1][$j] > $dp[$i][$j - 1]) {
            $i--;
        } else {
            $j--;
        }
    }

    return $lcs;
}

package main

func getLcs(s1, s2 string) string {
    m, n := len(s1), len(s2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if s1[i-1] == s2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }

    // Reconstruct LCS
    var lcs []byte
    i, j := m, n
    for i > 0 && j > 0 {
        if s1[i-1] == s2[j-1] {
            lcs = append(lcs, s1[i-1])
            i--
            j--
        } else if dp[i-1][j] > dp[i][j-1] {
            i--
        } else {
            j--
        }
    }
    // Reverse the result
    for l, r := 0, len(lcs)-1; l < r; l, r = l+1, r-1 {
        lcs[l], lcs[r] = lcs[r], lcs[l]
    }
    return string(lcs)
}
## Задача 2: Edit Distance (Levenshtein)

Условие: минимальное количество операций (вставка, удаление, замена) для преобразования s1 в s2.

"horse" -> "ros"
horse -> rorse (замена h->r)
rorse -> rose  (удаление r)
rose  -> ros   (удаление e)
Ответ: 3

Рекуррентность

Если s1[i-1] == s2[j-1]:
    dp[i][j] = dp[i-1][j-1]           # Символы равны, ничего не делаем
Иначе:
    dp[i][j] = 1 + min(
        dp[i-1][j],     # Удаление из s1
        dp[i][j-1],     # Вставка в s1
        dp[i-1][j-1]    # Замена
    )
PHPGo
<?php
declare(strict_types=1);

function minDistance(string $word1, string $word2): int
{
    $m = strlen($word1);
    $n = strlen($word2);
    $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));

    // Base cases
    for ($i = 0; $i <= $m; $i++) {
        $dp[$i][0] = $i; // Delete all characters from word1
    }
    for ($j = 0; $j <= $n; $j++) {
        $dp[0][$j] = $j; // Insert all characters of word2
    }

    for ($i = 1; $i <= $m; $i++) {
        for ($j = 1; $j <= $n; $j++) {
            if ($word1[$i - 1] === $word2[$j - 1]) {
                $dp[$i][$j] = $dp[$i - 1][$j - 1];
            } else {
                $dp[$i][$j] = 1 + min(
                    $dp[$i - 1][$j],      // delete
                    $dp[$i][$j - 1],      // insert
                    $dp[$i - 1][$j - 1]   // replace
                );
            }
        }
    }

    return $dp[$m][$n];
}

package main

func minDistance(word1, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    // Base cases
    for i := 0; i <= m; i++ {
        dp[i][0] = i // Delete all characters from word1
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = j // Insert all characters of word2
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = 1 + min(
                    dp[i-1][j],    // delete
                    dp[i][j-1],    // insert
                    dp[i-1][j-1],  // replace
                )
            }
        }
    }

    return dp[m][n]
}
Визуализация для "horse" -> "ros": 
      ""  r  o  s
  ""   0  1  2  3
  h    1  1  2  3
  o    2  2  1  2
  r    3  2  2  2
  s    4  3  3  2
  e    5  4  4  3  <- ответ

Задача 3: Longest Palindromic Subsequence

PHPGo
<?php
declare(strict_types=1);

function longestPalindromeSubseq(string $s): int
{
    $n = strlen($s);
    // dp[i][j] = length of LPS in s[i..j]
    $dp = array_fill(0, $n, array_fill(0, $n, 0));

    for ($i = 0; $i < $n; $i++) {
        $dp[$i][$i] = 1; // Each character is a palindrome of length 1
    }

    for ($length = 2; $length <= $n; $length++) {
        for ($i = 0; $i <= $n - $length; $i++) {
            $j = $i + $length - 1;
            if ($s[$i] === $s[$j]) {
                $dp[$i][$j] = $dp[$i + 1][$j - 1] + 2;
            } else {
                $dp[$i][$j] = max($dp[$i + 1][$j], $dp[$i][$j - 1]);
            }
        }
    }

    return $dp[0][$n - 1];
}

// s = "bbbab"
// LPS = "bbbb", length 4

package main

func longestPalindromeSubseq(s string) int {
    n := len(s)
    // dp[i][j] = length of LPS in s[i..j]
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
        dp[i][i] = 1 // Each character is a palindrome of length 1
    }

    for length := 2; length <= n; length++ {
        for i := 0; i <= n-length; i++ {
            j := i + length - 1
            if s[i] == s[j] {
                dp[i][j] = dp[i+1][j-1] + 2
            } else {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
            }
        }
    }

    return dp[0][n-1]
}

// s = "bbbab"
// LPS = "bbbb", length 4
Альтернатива: LPS = LCS(s, reverse(s)).

Задача 4: Longest Palindromic Substring

PHPGo
<?php
declare(strict_types=1);

function longestPalindrome(string $s): string
{
    $n = strlen($s);
    if ($n < 2) {
        return $s;
    }

    $start = 0;
    $maxLen = 1;

    // dp[i][j] = true if s[i..j] is a palindrome
    $dp = array_fill(0, $n, array_fill(0, $n, false));

    for ($i = 0; $i < $n; $i++) {
        $dp[$i][$i] = true;
    }

    for ($i = 0; $i < $n - 1; $i++) {
        if ($s[$i] === $s[$i + 1]) {
            $dp[$i][$i + 1] = true;
            $start = $i;
            $maxLen = 2;
        }
    }

    for ($length = 3; $length <= $n; $length++) {
        for ($i = 0; $i <= $n - $length; $i++) {
            $j = $i + $length - 1;
            if ($s[$i] === $s[$j] && $dp[$i + 1][$j - 1]) {
                $dp[$i][$j] = true;
                if ($length > $maxLen) {
                    $start = $i;
                    $maxLen = $length;
                }
            }
        }
    }

    return substr($s, $start, $maxLen);
}

package main

func longestPalindrome(s string) string {
    n := len(s)
    if n < 2 {
        return s
    }

    start, maxLen := 0, 1

    // dp[i][j] = true if s[i..j] is a palindrome
    dp := make([][]bool, n)
    for i := range dp {
        dp[i] = make([]bool, n)
        dp[i][i] = true
    }

    for i := 0; i < n-1; i++ {
        if s[i] == s[i+1] {
            dp[i][i+1] = true
            start = i
            maxLen = 2
        }
    }

    for length := 3; length <= n; length++ {
        for i := 0; i <= n-length; i++ {
            j := i + length - 1
            if s[i] == s[j] && dp[i+1][j-1] {
                dp[i][j] = true
                if length > maxLen {
                    start = i
                    maxLen = length
                }
            }
        }
    }

    return s[start : start+maxLen]
}
Более эффективный подход (expand around center):
PHPGo
<?php
declare(strict_types=1);

function longestPalindromeExpand(string $s): string
{
    $expand = function (int $left, int $right) use ($s): string {
        $len = strlen($s);
        while ($left >= 0 && $right < $len && $s[$left] === $s[$right]) {
            $left--;
            $right++;
        }
        return substr($s, $left + 1, $right - $left - 1);
    };

    $result = '';
    for ($i = 0; $i < strlen($s); $i++) {
        $odd = $expand($i, $i);        // Odd length
        $even = $expand($i, $i + 1);   // Even length

        if (strlen($odd) > strlen($result)) {
            $result = $odd;
        }
        if (strlen($even) > strlen($result)) {
            $result = $even;
        }
    }

    return $result;
}

package main

func longestPalindromeExpand(s string) string {
    expand := func(left, right int) string {
        for left >= 0 && right < len(s) && s[left] == s[right] {
            left--
            right++
        }
        return s[left+1 : right]
    }

    result := ""
    for i := 0; i < len(s); i++ {
        odd := expand(i, i)      // Odd length
        even := expand(i, i+1)   // Even length

        if len(odd) > len(result) {
            result = odd
        }
        if len(even) > len(result) {
            result = even
        }
    }

    return result
}
## Задача 5: Regular Expression Matching
PHPGo
<?php
declare(strict_types=1);

function isMatch(string $s, string $p): bool
{
    $m = strlen($s);
    $n = strlen($p);
    $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, false));
    $dp[0][0] = true;

    // Base case: a* can match empty string
    for ($j = 1; $j <= $n; $j++) {
        if ($p[$j - 1] === '*') {
            $dp[0][$j] = $dp[0][$j - 2];
        }
    }

    for ($i = 1; $i <= $m; $i++) {
        for ($j = 1; $j <= $n; $j++) {
            if ($p[$j - 1] === '.' || $p[$j - 1] === $s[$i - 1]) {
                $dp[$i][$j] = $dp[$i - 1][$j - 1];
            } elseif ($p[$j - 1] === '*') {
                $dp[$i][$j] = $dp[$i][$j - 2]; // Zero occurrences
                if ($p[$j - 2] === '.' || $p[$j - 2] === $s[$i - 1]) {
                    $dp[$i][$j] = $dp[$i][$j] || $dp[$i - 1][$j]; // One+ occurrences
                }
            }
        }
    }

    return $dp[$m][$n];
}

package main

func isMatch(s, p string) bool {
    m, n := len(s), len(p)
    dp := make([][]bool, m+1)
    for i := range dp {
        dp[i] = make([]bool, n+1)
    }
    dp[0][0] = true

    // Base case: a* can match empty string
    for j := 1; j <= n; j++ {
        if p[j-1] == '*' {
            dp[0][j] = dp[0][j-2]
        }
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if p[j-1] == '.' || p[j-1] == s[i-1] {
                dp[i][j] = dp[i-1][j-1]
            } else if p[j-1] == '*' {
                dp[i][j] = dp[i][j-2] // Zero occurrences
                if p[j-2] == '.' || p[j-2] == s[i-1] {
                    dp[i][j] = dp[i][j] || dp[i-1][j] // One+ occurrences
                }
            }
        }
    }

    return dp[m][n]
}
## Сводная таблица DP на строках
Задача Сложность Подход
LCS O(m*n) 2D DP, совпадение символов
Edit Distance O(m*n) 2D DP, min из 3 операций
Longest Palindromic Subseq O(n²) 2D DP, интервалы
Longest Palindromic Substring O(n²) / O(n) DP или expand around center
Regular Expression O(m*n) 2D DP с обработкой * и .
Wildcard Matching O(m*n) 2D DP с обработкой * и ?

Запомни: DP на строках почти всегда использует 2D таблицу dp[i][j] где i и j — позиции в двух строках. Заполнение идёт по строкам или по длине подстроки. LCS и Edit Distance — две базовые задачи, из которых выводятся многие другие. Palindrome задачи можно свести к LCS(s, reverse(s)).

Итоги

  1. LCS: dp[i][j] = dp[i-1][j-1]+1 при совпадении, иначе max
  2. Edit Distance: dp[i][j] = 1 + min(delete, insert, replace)
  3. Palindrome Subseq = LCS(s, reverse(s))
  4. Palindrome Substring: expand around center O(n^2) проще DP
  5. Все задачи: O(m*n) или O(n^2), можно оптимизировать память до O(min(m,n))

Проверь себя

🧪

В задаче Regular Expression Matching, что делает паттерн 'a*' при сопоставлении со строкой?

🧪

Чему равно Edit Distance (расстояние Левенштейна) между 'horse' и 'ros'?

🧪

Какой подход к нахождению наибольшей палиндромной подстроки проще в реализации и имеет ту же сложность O(n²)?

🧪

Как можно найти длину наибольшей палиндромной подпоследовательности строки s?

🧪

Какова длина наибольшей общей подпоследовательности (LCS) строк 'abcde' и 'ace'?

Связанные темы

Алгоритм Дейкстры

Связанная тема

Кейс: Collaborative Editor

Связанная тема