Блог

Я собираюсь просмотреть некоторые сообщения об алгоритме. При просмотре у меня возникли сомнения, почему мы добавили 1 в приведенный ниже код при возврате окончательного решения.

 import sys 

# Recursive function to find minimum  
# number of insertions 
def findMinInsertions(str, l, h): 

    # Base Cases 
    if (l > h): 
        return sys.maxsize 
    if (l == h): 
        return 0
    if (l == h - 1): 
        return 0 if(str[l] == str[h]) else 1

    # Check if the first and last characters are 
    # same. On the basis of the comparison result,  
    # decide which subrpoblem(s) to call 

    if(str[l] == str[h]): 
        return findMinInsertions(str, l   1, h - 1) 
    else: 

        **return (min(findMinInsertions(str, l, h - 1), 
                findMinInsertions(str, l   1, h))   1)** 

# Driver Code 
if __name__ == "__main__": 

    str = "abc"
    print(findMinInsertions(str, 0, len(str) - 1)) 
  

 findMinInsertions(str, l, h - 1)
  

это минимальное количество вставок после вставки последнего символа.

 findMinInsertions(str, l   1, h)
  

это минимальное количество вставок после вставки первого символа.

 min(findMinInsertions(str, l, h - 1), findMinInsertions(str, l   1, h)) # (a)
  

это минимальное количество вставок после вставки первого или последнего символа. Чтобы получить минимальное количество вставок, вы можете взять минимальное количество вставок после того, как был вставлен один символ (a) и добавить одну вставку (поскольку один символ уже был вставлен).

1 используется для подсчета. нам нужно добавить при возврате обратно к родительскому узлу (начать с 0 { вернуть 0 } 1 ). а затем выполнить минимум два рекурсивных вызова.

Алгоритм не находит минимальное количество вставок во время сортировки вставок, а просто дает верхнюю границу количества вставок. Это легко проверить, просто запустив алгоритм для строки «abc» и увидев, что результат равен 2, в то время как реальный минимум вставок равен 0.

Давайте посмотрим на рекурсивный шаг:

 if(str[l] == str[h]): 
    return findMinInsertions(str, l   1, h - 1) 
else: 

    return (min(findMinInsertions(str, l, h - 1), 
            findMinInsertions(str, l   1, h))   1)
  

если str [l] == str[h], минимальное количество вставок определяется значениями символов между ними, потому что str [l] и str [h] могут оставаться в их относительном положении (то есть str [h] останется справа от str [l]), следовательно, мы будем перемещать / вставлять только символы между индексами l и h.

Как только вы поймете, что происходит в случае равенства, вы сможете понять, что в случае неравенства существует вероятность перемещения одного из символов str[l] или str[h].

Обратите внимание, что, поскольку это всего лишь вероятность перемещения символа, алгоритм выдает верхнюю границу количества вставок, а не минимальную.