时间戳

首页 > 解决方案 > 优化这个递归函数（动态规划）

python - 优化这个递归函数（动态规划）

问题描述

我正在解决一个非常简单的算法问题，它要求递归和记忆。下面的代码工作正常，但不符合时间限制。有人建议我优化尾递归，但它不是尾递归。这只是学习材料，不是作业。

问题

• 如果下雨，蜗牛每天可以爬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))

标签： pythonalgorithmrecursiondynamic-programming

解决方案

很简单。所以这只是一个提示。对于初始零件集：

# 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]

推荐阅读