我正在浏览一些算法帖子。在审查时,我怀疑为什么我们在返回最终解决方案时在下面的代码中添加了 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) 并添加一次插入(因为已经插入了一个字符)。
关于python - 为什么要在解决方案中添加 +1,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55275299/