Редактировать расстояние Рекурсия против динамического программирования в Python ⇐ Python

[Anonymous]

Решение методом грубой силы для определения расстояния редактирования основано на рекурсии

Код: Выделить всё

def levi_rec(a, b):
if a == "":
return len(b)
if b == "":
return len(a)
if a[0] == b[0]:
return levi_rec(a[1:], b[1:])
return 1 + min(
levi_rec(a[1:], b),      # deletion
levi_rec(a, b[1:]),      # insertion
levi_rec(a[1:], b[1:])   # substitution
)

Один из способов оптимизации решения — использовать динамическое программирование на основе 2D-массива (копия из Neetcode)

Код: Выделить всё

def levi_dp_2d(a,b):
two_dim_array = np.zeros((len(a) + 1, len(b) + 1))

# initialise the base case that a or b is empty string
for j in range (len(b) + 1):
# fill up the bottom row
two_dim_array[len(a)][j] = len(b) - j
for i in range (len(a) + 1):
# fill up the last column
two_dim_array[i][len(b)] = len(a) - i

# dynamic programming part
for i in range(len(a) - 1, -1, -1):
for j in range(len(b) - 1, -1, -1):
if a[i] == b[j]:
two_dim_array[i][j] = two_dim_array[i + 1][j + 1]
else:
two_dim_array[i][j] = 1 + min(
two_dim_array[i + 1][j + 1],
two_dim_array[i + 1][j],
two_dim_array[i][j + 1]
)

return two_dim_array[0][0]

И у меня есть два естественных вопроса:

• Теоретически, levi_rec(a,b) =?= levi_dp_2d(a,b) для любых возможных строк (a,b)? Если да, то как это доказать? моя интуиция подсказывает, что нужно использовать индукцию, но я не знаю, с чего начать.
• На практике (или даже теоретически) существует ли какая-нибудь пара строк (a,b) такая, что levi_rec(a,b) != levi_dp_2d(a,b)? Давайте не будем рассматривать большой тестовый пример, т. е. и a, и b могут быть короткими строками.

Подробнее здесь: https://stackoverflow.com/questions/798 ... -in-python