Оптимизация этой рекурсивной функции (динамическое программирование) - PullRequest
Новая
       10

Оптимизация этой рекурсивной функции (динамическое программирование)

0 голосов
/ 26 июня 2019

Я решаю очень простой алгоритм, который запрашивает рекурсию и запоминание. Код ниже работает нормально, но не соответствует ограничениям по времени. Кто-то посоветовал мне оптимизировать хвостовую рекурсию, но это не хвостовая рекурсия.

Вопрос

• Улитка может подниматься на 2 метра в 1 день, если идет дождь, в противном случае на 1 метр

• Вероятность дождя в день составляет 75%.

• Учитывая количество дней (<= 1000) и рост (<= 1000), вычислите вероятность того, что улитка может выбраться из колодца (забраться больше, чем высота колодца) </p>

Этот код 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))

1 Ответ

1 голос
/ 26 июня 2019

Это просто.Так что это просто подсказка.Для набора начальных частей: 

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