爪哇 - 通過二維數組

路徑最大總和基本上我有去類似於這樣一個問題：爪哇 - 通過二維數組

有由2D，方形陣列表示草莓植株的花園。每個植物（每個元素）都有一些草莓。您從數組的左上角開始，只能向右或向下移動。我需要設計一個遞歸方法來計算通過花園的路徑，然後輸出哪個產生最多的草莓。

我想我真的很簡單的遞歸問題的理解，但這個問題已經超出了我的頭。我並不確定從哪裏開始或到哪裏去創建一個遞歸方法。

任何與代碼有關的幫助或幫助我理解這個問題背後的概念是非常感謝。謝謝。

來源

2012-07-23 user1547050

它是否必須遞歸？迭代在這裏會更簡單。 – 2012-07-23 22:17:34

是的，它必須是遞歸的。 – user1547050 2012-07-23 22:42:57

那麼，dasblinkenlight的答案效果很好，你只需要跟蹤是否下降或者右邊會產生更大的數字。 – 2012-07-23 22:47:58

像dasblinkenlight說的，最有效的方法是使用記憶或動態編程技術。我傾向於更喜歡動態編程，但我會在這裏使用純遞歸。

答案的中心圍繞着一個基本問題的答案：「如果我在我的領域的r行和c列的廣場上，我如何評估從左上角到這裏的路徑，草莓是最大化的？「

要實現的關鍵是在r行和c列中只有兩種方式可以進入圖中：或者我可以從上面得到，使用第r-1行和c列中的圖，或者我可以得到從那邊，使用第r行和第c-1列的圖。在此之後，你只需要確保你知道你的基礎的情況下...這意味着，從根本上，我純粹是遞歸的版本會是這樣的：

int[][] field;  
int max(int r, int c) { 
    //Base case 
    if (r == 0 && c == 0) { 
     return field[r][c]; 
    } 
    //Assuming a positive number of strawberries in each plot, otherwise this needs 
    //to be negative infinity 
    int maxTop = -1, maxLeft = -1; 
    //We can't come from the top if we're in the top row 
    if (r != 0) { 
     maxTop = field[r-1][c]; 
    } 
    //Similarly, we can't come from the left if we're in the left column 
    if (c != 0) { 
     maxLeft = field[r][c-1]; 
    } 
    //Take whichever gives you more and return.. 
    return Math.max(maxTop, maxLeft) + field[r][c]; 
}

呼叫MAX（R-1，C-1）得到你的答案。注意這裏有很多低效率;你會通過使用動態編程（我將在下面提供）或memoization（已經定義）做得更好。但要記住的是，DP和memoization技術都是來自這裏使用的遞歸原理的更有效的方法。

DP：

int maxValue(int[][] field) { 
    int r = field.length; 
    int c = field[0].length; 
    int[][] maxValues = new int[r][c]; 
    for (int i = 0; i < r; i++) { 
     for (int j = 0; j < c; j++) { 
      if (i == 0 && j == 0) { 
       maxValues[i][j] = field[i][j]; 
      } else if (i == 0) { 
       maxValues[i][j] = maxValues[i][j-1] + field[i][j]; 
      } else if (j == 0) { 
       maxValues[i][j] = maxValues[i-1][j] + field[i][j]; 
      } else { 
       maxValues[i][j] = Math.max(maxValues[i][j-1], maxValues[i-1][j]) + field[i][j]; 
      } 
     } 
    } 
    return maxValues[r-1][c-1]; 
}

在這兩種情況下，如果要重新創建實際的路徑，只是不停地與對應的布爾值二維表「難道我來自上方或左邊的」？如果最多的草莓路徑來自上面，則變爲真實，否則爲假。這可以讓您在計算後追溯修補程序。

請注意，這仍然是主要的遞歸：在每一步，我們回顧我們以前的結果。我們只是緩存了以前的結果，所以我們不會浪費大量的工作，而且我們正在以一個明智的順序攻擊子問題，以便我們可以隨時解決它們。有關動態編程的更多信息，請參閱Wikipedia。

來源

2012-07-23 23:00:08 DivineWolfwood

你可能意思是'return maxValues [r-1] [c-1];' – Quixotic 2012-12-08 16:28:47

哎呀，謝謝！ – DivineWolfwood 2014-03-13 02:24:53

嗨DivineWolfwood，你的例子很有趣。但是，我想看看左右兩邊是什麼？ – Doro 2014-04-05 17:07:48

你可以使用memoization。這裏是類似Java的僞數據（memo,R和C被假定爲可用於max方法的實例變量）。

int R = 10, C = 20; 
int memo[][] = new int[R][C]; 
for (int r=0 ; r != R ; r++) 
    for (int c = 0 ; c != C ; c++) 
     memo[r][c] = -1; 
int res = max(0, 0, field); 

int max(int r, int c, int[][] field) { 
    if (memo[r][c] != -1) return memo[r][c]; 
    int down = 0; right = 0; 
    if (r != R) down = max(r+1, c, field); 
    if (c != C) right = max(r, c+1, field); 
    return memo[r][c] = (field[r][c] + Math.max(down, right)); 
}

來源

2012-07-23 22:21:15 dasblinkenlight

嘿，你可以幫助我，但一個** [有點複雜的任務]（http://stackoverflow.com/q/42706957/2650174）**。 – 2017-03-09 23:12:17

您可以使用DP製表方法解決此問題，您可以使用該製表方法將空間從O（m * n）節省到O（n）。使用DP記憶，您需要m * n矩陣來存儲中間值。以下是我的Python代碼。希望它可以幫助。

def max_path(field): 
    dp = [sum(field[0][:i]) for i in range(1, len(field[0]) + 1)] 
    for i in range(1, len(field)): 
     for j in range(len(dp)): 
      dp[j] = min(dp[j], dp[j - 1] if j > 0 else float('inf')) + field[i][j] 
    return dp[-1]

來源

2018-02-15 22:37:15

爪哇 - 通過二維數組

回答

相關問題