正在通过一些算法帖子。在审查时，我怀疑为什么我们在返回最终解决方案的同时在下面的代码中添加了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）采取最少的插入次数，然后添加一次插入（因为已经插入了一个字符）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句