我正在求解一个非常简单的算法问题,要求递归和记忆。下面的代码正常运行,但不符合时间限制。有人建议我优化尾部递归,但这不是尾部递归。这只是一种研究材料,而不是作业。
问题
•如果下雨,蜗牛可以每天攀升2m,否则可以攀升1M。
•每天下雨的可能性为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))
这很简单。所以这只是一个提示。对于intal部分集:
# suppose cache is allocated
cache[1][1] = 0.25
cache[1][2] = 0.75
for i in range(3,targetHeight+1):
cache[1][i] = 0
for i in range(days+1):
cache[i][1] = 1
cache[i][0] = 1
,然后尝试使用初始化值重写递归部分(您应该迭代自下而上,喜欢以下(。最后,返回cache[days][targetHeight]
的值。
for i in range(2, days+1):
for j in range(2, targetHeight+1):
cache[i][j] = 0.75 * cache[i-1][j-2] + 0.25 * cache[i-1][j-1]