Как использовать матрицу Dynami c в программировании Dynami c?

Question

Обычно, решая проблему с помощью техники динамического программирования c, вы разбиваете ее на набор более простых подзадач, решая каждую из этих подзадач только один раз и сохраняя их решения, используя структуру данных на основе памяти (массив , map, et c) ('Dynami c Matrix').

Например, Здесь существует алгоритм, использующий Dynami c Программирование для определения максимальной прибыли по покупка и продажа акций не более k раз. Я изменил алгоритм для возврата всей двумерной матрицы (транзакции k * дней n), и вот пример:

def maxProfit(price, n, k):

    # Table to store results of subproblems
    # profit[t][i] stores maximum profit
    # using atmost t transactions up to
    # day i (including day i)
    profit = np.zeros((k + 1, n)) 

    # Fill the table in bottom-up fashion
    #for i in range(1, k + 1):
    prevDiff = np.zeros(k) + float('-inf')

    for j in range(1, n):
        temp = prevDiff
        prevDiff = np.maximum(prevDiff, profit[0:k, j - 1] - price[j - 1])
        profit[1:k + 1, j] = np.maximum(profit[1:k + 1, j - 1], price[j] + prevDiff)

    return profit

# Driver Code
if __name__ == "__main__": 

    price = [100, 99, 0, 5, 6, 50, 100, 35, 33, 0, 70, 1000, 500, 400, 0, 225, 700, 2000, 800]
    k = 3
    n = len(price)
    profit = maxProfit(price, n, k)
    print("Maximum profit is:")
    print(profit)

Вывод:

[   0.    0.    0.    0.    0.    0.    0.    0.    0.    0.    0.    0.     0.    0.    0.    0.    0.    0.    0.]  
[   0.    0.    0.    5.    6.   50.  100.  100.  100.  100.  100. 1000.  1000. 1000. 1000. 1000. 1000. 2000. 2000.]  
[   0.    0.    0.    5.    6.   50.  100.  100.  100.  100.  170. 1100.  1100. 1100. 1100. 1225. 1700. 3000. 3000.]  
[   0.    0.    0.    5.    6.   50.  100.  100.  100.  100.  170. 1100.  1100. 1100. 1100. 1325. 1800. 3100. 3100.]  

Мой вопрос Как вы можете определить, в каких парах дней (i, j) (покупка в день i, продажа в день j) имели место транзакции?

Другая проблема, которая использует динамическое c программирование, - это Egg Dropping Puzzle . В этой задаче вопрос заключается в том, как найти этажи, на которых вы бросаете яйца, используя матрицу Dynami c?