Unique Paths, LCS, Edit Distance.
Двумерное динамическое программирование. Unique Paths, LCS, Edit Distance.
Условие:
Сколькими различными путями робот может достичь правого нижнего угла сетки 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]Объяснение:
Сложность: O(m × n)
Условие: Найдите путь с минимальной суммой от левого верхнего до правого нижнего угла.
Решение:
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)
Условие: Верните длину наибольшей общей подпоследовательности двух строк.
Решение:
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]Объяснение:
Сложность: O(m × n)
Условие: Найдите минимальное количество операций (вставка, удаление, замена) для преобразования 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)
| Задача | Формула |
|---|---|
| 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 = [[0] * n for _ in range(m)] # Размеры без +1!
# ✅ Правильно
dp = [[0] * (n + 1) for _ in range(m + 1)]# ❌ Неправильно
dp[0][0] = 0 # Но нет инициализации первой строки/столбца!
# ✅ Правильно
dp[i][0] = i # Удалить все символы
dp[0][j] = j # Вставить все символыDynamic Programming: 2D — задачи с двумя измерениями.
Ключевые приёмы:
Вопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.