Dynamic Programming: 2D

Двумерное динамическое программирование. Unique Paths, LCS, Edit Distance.

#1. Unique Paths (LeetCode 62) 🟦 Medium

Ссылка: https://leetcode.com/problems/unique-paths/

Условие: Сколькими различными путями робот может достичь правого нижнего угла сетки m x n?

Решение:

def uniquePaths(m, n):
    dp = [[1] * n for _ in range(m)]

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]

    return dp[m-1][n-1]

Объяснение:

dp[i][j] = dp[i-1][j] + dp[i][j-1]
Базовый случай: первая строка и столбец = 1

Сложность: O(m × n)

#2. Minimum Path Sum (LeetCode 64) 🟦 Medium

Ссылка: https://leetcode.com/problems/minimum-path-sum/

Условие: Найдите путь с минимальной суммой от левого верхнего до правого нижнего угла.

Решение:

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]

    dp[0][0] = grid[0][0]

    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]

    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

    return dp[m-1][n-1]

Сложность: O(m × n)

#3. Longest Common Subsequence (LeetCode 1143) 🟦 Medium

Ссылка: https://leetcode.com/problems/longest-common-subsequence/

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

Решение:

def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[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]

Объяснение:

Если символы равны: dp[i][j] = dp[i-1][j-1] + 1
Иначе: max(пропустить символ text1, пропустить символ text2)

Сложность: O(m × n)

#4. Edit Distance (LeetCode 72) 🔴 Hard

Ссылка: https://leetcode.com/problems/edit-distance/

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

Решение:

def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            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]

Сложность: O(m × n)

#5. Шпаргалка

Задача	Формула
Unique Paths	dp[i][j] = dp[i-1][j] + dp[i][j-1]
Min Path Sum	min(сверху, слева) + grid[i][j]
LCS	dp[i-1][j-1] + 1 если равны
Edit Distance	1 + min(delete, insert, replace)

#6. ⚠️ Common Mistakes

#❌ Ошибка 1: Неправильная инициализация LCS

# ❌ Неправильно
dp = [[0] * n for _ in range(m)]  # Размеры без +1!

# ✅ Правильно
dp = [[0] * (n + 1) for _ in range(m + 1)]

#❌ Ошибка 2: Неправильные базовые случаи Edit Distance

# ❌ Неправильно
dp[0][0] = 0  # Но нет инициализации первой строки/столбца!

# ✅ Правильно
dp[i][0] = i  # Удалить все символы
dp[0][j] = j  # Вставить все символы

#7. Заключение

Dynamic Programming: 2D — задачи с двумя измерениями.

Ключевые приёмы:

Unique Paths: сумма сверху и слева
LCS: +1 если символы равны
Edit Distance: 3 операции

Задача

Формула

Unique Paths

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Min Path Sum

min(сверху, слева) + grid[i][j]

LCS

dp[i-1][j-1] + 1 если равны

Edit Distance

1 + min(delete, insert, replace)

DP: 2D