Перевод с Рекурсии на Динамическое программирование

Question

Есть задача, решил с помощью рекурсии с запоминанием результата:

input()
a = list(map(int,input().split()))
c = {}
def game_2(row_of_numbers, player_turn):
    global c
    left = row_of_numbers[0]
    right = row_of_numbers[-1]
    if str(row_of_numbers)+'+'+str(player_turn) in c.keys():
        return c[str(row_of_numbers)+'+'+str(player_turn)]
    else:
        if len(row_of_numbers) == 2:
            if player_turn == 1:
                a = max(right,left) - min(right,left)
                c[str(row_of_numbers)+'+'+str(player_turn)] = a
                return a
            elif player_turn == 2:
                a = min(right,left) - max(left,right)
                c[str(row_of_numbers)+'+'+str(player_turn)] = a
                return min(right,left) - max(left,right)
        else:
            if player_turn == 1:
                left1 = left + game_2(row_of_numbers[1:], 2)
                right1 = right + game_2(row_of_numbers[0:len(row_of_numbers)-1],2)
                a = max(left1,right1)
                c[str(row_of_numbers)+'+'+str(player_turn)] = a
                return a
            elif player_turn == 2:
                left1 = -left + game_2(row_of_numbers[1:], 1)
                right1 = -right + game_2(row_of_numbers[0:len(row_of_numbers)-1],1) 
                a = min(left1,right1)
                c[str(row_of_numbers)+'+'+str(player_turn)] = a   
                return a
b = game_2(a, 1)
if b == 0:
    print(0)
elif b == 1:
    print(1)
elif b>0:
    print(1)
elif b<0:
    print(2)

Очень хотелось бы узнать метод решения на динамическом программировании. Не очень дружу с ДП) в обсуждении написано, что нужен массив, где arr[start][end] = лучшее решение с позиции start по позицию end (могу ошибаться).

Answer 1

Динамическое программирование - важная часть теории сложности вычислений. Есть много хитрых задач и техник. Но идея которая лежит внутри очень проста: если вы один раз вычислили функцию с какими-то аргументами, не нужно вычислять её ещё раз. Все вызовы кешируются. На Python кеш можно применить к любой функции, аргументы которой могут быть ключами в dict. game_2 не подходит, первый аргумент list. Если вы замените его на tuple, то заработает декоратор functools.lru_cache(maxsize=None).

Я не хочу тут принизить важность ДП. Но важность ДП не в том как организовать кеш, а в том как рекурсивно описать решение так чтобы кеш оказался эффективным.

Пример. Простая функция вычисления чисел Фибоначчи и динамическое программирование для решения той же задачи:

import functools
import time


def elapsed_time(f):
    start = time.time()
    result = f()
    finish = time.time()
    return result, finish - start


def fib1(n):
    if n == 1:
        return 1
    if n == 2:
        return 1
    return fib1(n - 2) + fib1(n - 1)


@functools.lru_cache(maxsize=None)
def fib2(n):
    if n == 1:
        return 1
    if n == 2:
        return 1
    return fib2(n - 2) + fib2(n - 1)


for n in range(1, 100):
    f1, t1 = elapsed_time(lambda: fib1(n))
    f2, t2 = elapsed_time(lambda: fib2(n))
    assert f1 == f2
    print(f'{t1:.3f} {t2:.3f} fib({n:2}) = {f1}')

Время различается разительно (экспонента против линейной сложности с ДП):

...
0.001 0.000 fib(18) = 2584
0.001 0.000 fib(19) = 4181
0.002 0.000 fib(20) = 6765
0.003 0.000 fib(21) = 10946
0.005 0.000 fib(22) = 17711
0.007 0.000 fib(23) = 28657
0.012 0.000 fib(24) = 46368
0.019 0.000 fib(25) = 75025
0.032 0.000 fib(26) = 121393
0.049 0.000 fib(27) = 196418
0.080 0.000 fib(28) = 317811
0.129 0.000 fib(29) = 514229
0.210 0.000 fib(30) = 832040
0.336 0.000 fib(31) = 1346269
0.544 0.000 fib(32) = 2178309
0.877 0.000 fib(33) = 3524578
1.413 0.000 fib(34) = 5702887
2.346 0.000 fib(35) = 9227465
3.698 0.000 fib(36) = 14930352
5.975 0.000 fib(37) = 24157817
9.704 0.000 fib(38) = 39088169

БЛОГ НА HUSL

Перевод с Рекурсии на Динамическое программирование

Ответы (1 шт):