如何將以下遞歸dp轉換爲迭代

Question

我試圖將以下遞歸代碼轉換爲自下而上/迭代動態編程。 但是我無法弄清楚我應該迭代的順序，因爲狀態依賴於下一個和上一個索引。

matrix = [[-1, 4, 5, 1], 
     [ 2,-1, 2, 4], 
     [ 3, 3,-1, 3], 
     [ 4, 2, 1, 2]] 
rows = len(matrix) 
cols = len(matrix[0]) 
cache = {} 

def maxsum(dir, x, y): 
    key = (dir, x, y) 
    if key in cache: return cache[key] 
    base = matrix[y][x] 
    if x < cols-1: 
     best = base + maxsum(2, x+1, y) 
    else: 
     best = base 
    if dir != 0 and y > 0: 
     best = max(best, base + maxsum(1, x, y-1)) 
    if dir != 1 and y < rows-1: 
     best = max(best, base + maxsum(0, x, y+1)) 
    cache[key] = best 
    return best 

是否有可能將此代碼轉換爲迭代？ 如果是，請幫我解決迭代排序問題。

'dir'可以從0-2獲得值。

x和y爲1和1000之間

我不想用棧來解決這個問題。我想用一般的迭代循環來解決這個問題，就像我們在自下而上的動態編程中所做的那樣。

Answer 1

總的想法是設想遞歸調用圖/樹和葉節點是什麼;那麼，迭代解決方案只是從葉節點開始，並迭代地構建樹，一直到根。

當然，這說起來容易做起來難，但往往存在結構上的問題，可以幫助你的直覺。在這種特殊情況下，這是2D網格。

直覺

通過建立一些直覺讓我們開始。查看代碼中的分支。他們決定你是否在特定情況下遞解。他們對應什麼？ 你什麼時候不遞歸？爲了，它們是：

• 電網
• 電網
• 電網

我們需要建立這些第一底邊的頂部邊緣的右邊緣。

基本情況

問自己：在什麼情況下我們不是在所有遞歸？這是基本情況。在沒有特定的順序，它們是：

• 網格的右上角，並dir=1
• 格的右下角，並且dir=0

遞歸案件

最後，問問自己：從我們的價值開始，我們可以計算什麼？

• 的右上角，我們可以計算出整個右邊的dir=1
• 的右下角，我們可以計算出整個右邊爲dir=0

從這，然後我們可以計算dir=2的整個右邊緣。

現在我們已經填充了右邊的值，然後我們可以計算出什麼？記住上面的特殊情況。取決於右邊緣的只有的的單元格是緊鄰右邊緣左側的頂部和底部邊緣中的兩個單元格，分別爲dir=1和dir=0。

有了這個，我們現在可以計算右邊的第二列dir=1和dir=0，因此dir=2。

重複，直到找到想要的單元格的值。

守則

注：這是一個有點欠佳，因爲它填補了整個表，但它應該足以說明這個想法。

def fill(dir, x, y): 
    base = matrix[y][x] 
    if x < cols-1: 
     best = base + cache[2, x + 1, y] 
    else: 
     best = base 
    if dir != 0 and y > 0: 
     best = max(best, base + cache[1, x, y - 1]) 
    if dir != 1 and y < rows - 1: 
     best = max(best, base + cache[0, x, y + 1]) 
    cache[dir, x, y] = best 


def maxsum(dir, x, y): 
    for i in range(cols - 1, -1, -1): 
     for j in range(rows - 1, -1, -1): 
      fill(0, i, j) 
     for j in range(rows): 
      fill(1, i, j) 
     for j in range(rows): 
      fill(2, i, j) 
    return cache[dir, x, y]