为什么要在解决方案中添加 +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

+1 用来计数。我们需要添加 while returning 回到父节点（从 0 { return 0 }+ 1 开始）。然后取两个递归调用的最小值。

Answer 2

findMinInsertions(str, l, h - 1)

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

findMinInsertions(str, l + 1, h)

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

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

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

Answer 3

该算法在插入排序时没有找到最小插入次数，只是给出了插入次数的上限。通过简单地运行字符串 "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].

注意因为这只是一次移动角色的机会，所以算法产生插入次数的上限而不是最小值。

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

Why to added +1 in solution

python

algorithm

dynamic-programming

insertion-sort