python - 为什么要在解决方案中添加 +1

Question

我正在浏览一些算法帖子。在审查时，我怀疑为什么我们在返回最终解决方案时在下面的代码中添加了 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)) 

Answer 1

findMinInsertions(str, l, h - 1)

是插入最后一个字符后的最小插入次数。

findMinInsertions(str, l + 1, h)

是插入第一个字符后的最小插入次数。

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

是插入第一个字符或最后一个字符后的最小插入次数。要获得最少的插入次数，您可以在插入一个字符后获取最少的插入次数 (a) 并添加一次插入(因为已经插入了一个字符)。