Редактировать расстояние Рекурсия против динамического программирования в 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))

# initialize the base case that a or b is empty string
for j in range (len(b) + 1):

two_dim_array[len(a)][j] = len(b) - j  # fill up the bottom row

for i in range (len(a) + 1):

two_dim_array[i][len(b)] = len(a) - i  # fill up the last column

# 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]

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

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

2. На практике (или даже теоретически) существует ли пара строк (a,b) такая, что levi_rec(a,b) != levi_dp_2d(a,b)? Давайте не будем рассматривать большой тестовый пример, т. е. и a, и b могут быть короткими строками.

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