我正在解决一个非常简单的算法问题,需要递归和记忆。下面的代码工作正常,但不符合时间限制。有人建议我优化尾部递归,但它不是尾部递归。。这只是学习资料,不是家庭作业。你知道吗
问题
•如果下雨,蜗牛可以一天爬2米,否则可以爬1米。你知道吗
•每天下雨的概率为75%。你知道吗
•给定天数(<;=1000)和高度(<;=1000),计算蜗牛出井的概率(爬得比井高更多)
这个python代码是通过递归和记忆实现的。你知道吗
import sys
sys.setrecursionlimit(10000)
# Probability of success that snails can climb 'targetHeight' within 'days'
def successRate(days, targetHeight):
global cache
# edge case
if targetHeight <= 1:
return 1
if days == 1:
if targetHeight > 2:
return 0
elif targetHeight == 2:
return 0.75
elif targetHeight == 1:
return 0.25
answer = cache[days][targetHeight]
# if the answer is not previously calculated
if answer == -1:
answer = 0.75 * (successRate(days - 1, targetHeight - 2)) + 0.25 * (successRate(days - 1, targetHeight - 1))
cache[days][targetHeight] = answer
return answer
height, duration = map(int, input().split())
cache = [[-1 for j in range(height + 1)] for i in range(duration + 1)] # cache initialized as -1
print(round(successRate(duration, height),7))
这很简单。所以这只是一个暗示。 对于初始零件集:
然后尝试使用初始化的值重写递归部分(您应该自底向上迭代,如下所示)。最后,返回
cache[days][targetHeight]
的值。你知道吗相关问题 更多 >
编程相关推荐