Зачем добавлять +1 в решение - PullRequest
Новая
       26

Зачем добавлять +1 в решение

2 голосов
/ 21 марта 2019

Собираюсь через несколько алгоритмов постов.При просмотре я сомневаюсь, почему мы добавили 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))

Ответы [ 3 ]

0 голосов
/ 21 марта 2019 
findMinInsertions(str, l, h - 1)

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

findMinInsertions(str, l + 1, h)

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

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

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

0 голосов
/ 21 марта 2019

Алгоритм не находит минимальное количество вставок во время сортировки вставок, а просто дает верхнюю границу количества вставок.Это легко проверить, просто запустив алгоритм в строке «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].

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

0 голосов
/ 21 марта 2019

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

...