Учитывая списки последовательностей P и T. Я пытаюсь написать алгоритм (функция minNumOfTransformations(P,T) ), которая возвращает минимальное количество перемещений или преобразований, необходимых для перехода к T из P. Эти преобразования включают замену, вставку или удаление. Например. чтобы добраться до [0,2,4,5] из [0,1,2,3,5] требуется как минимум 2 преобразования; Добавление 1 и замена 4 на 3. Я пытаюсь сделать это с помощью динамического программирования на python.
def minNumOfTransformations(P, T):
# If first list is empty, the only option is to
# insert all the elements
if m==0:
return n
# If second list is empty, the only option is to
# remove all the characters of the first list
if n==0:
return m
# approach here is to solve simpler sub problems but this is where I get stuck
if P[m-1]==T[n-1]:
return minNumofTransformations(P[m-1], T[n-1])
пожалуйста, предоставьте весь ваш код. Оба m и n определены вне вашего вопроса (предположительно?).
Что мешает вам найти готовый ответ в Google, так это, вероятно, то, что вы не знаете, что то, что вы ищете, известно как расстояние Левенштейна и является стандартной метрикой для различия между последовательностями.
Существует Пакет Python, созданный специально для этого и реализованный на C, поэтому он, вероятно, будет быстрее, чем все, что вы напишете.
Если вы действительно хотите сделать это самостоятельно на Python, это поможет:
https://rosettacode.org/wiki/Levenshtein_distance#Python
Спасибо. Для подхода динамического программирования в Google указано, что временная сложность составляет O (нм). Вы знаете, почему это так?
Ну и какой у тебя вопрос?