背景 我今天接受了一次采訪，被問到以下問題。給你一個網格。 int [][] grid = { {0,0,0,2,5}, {0,0,0,1,5}, {0,1,1,1,1}, {2,0,0,0,0} };您從網格的左下角開始。你只能向上和向右。這個想法是到達右上角。你要走一條能給你帶來最大價值的道路。上面的輸出是 16我的解決方案public static int getPathMaxSum(int [][] grid){ int row = grid.length-1; int col = 0; int currentSum = grid[row][col]; return getMax(grid,currentSum,row,col);}public static int getMax(int [][] grid,int sum,int row,int col){ if((isTopRight(grid,row,col)) || (!isValid(grid,row,col))){ return sum; }else{ sum = sum + grid[row][col]; return Math.max(getMax(grid,sum,row-1,col),getMax(grid,sum,row,col+1)); }}public static boolean isTopRight(int [][] grid, int row, int col){ return row == 0 && col == grid[row].length-1;}public static boolean isValid(int [][] grid, int row, int col){ return (row >= 0 && row < grid.length) && (col >= 0 && col < grid[row].length);}我正在嘗試遞歸地解決這個問題。我認為我在每個位置都有 2 個可能的選擇，并且我想獲得這兩個選擇中的最大值，但由于某種原因我無法獲得正確的輸出。我有兩個輔助函數，它們檢查我的位置在網格內是否有效，以及我是否已經點擊了右上角，如果有，那么我就點擊了我的基本情況。我很想知道我哪里出錯了。
2 回答
慕桂英546537
TA貢獻1848條經驗 獲得超10個贊
sum您的方法中不需要參數。
我假設您已經了解自上而下的遞歸方法如何解決這個問題。但同樣為了完整起見，基本公式是：
您從 處的單元格開始row，獲取其值，然后向上或向右col查找。(row-1, col)(row, col+1)
所以結果將是：
grid[row][col] + Math.max( getMax( row-1, col, grid ), getMax( row, col+1, grid ) )
基本條件：
a）如果它位于右上角，即目的地，則無需遞歸，只需返回該單元格處的值即可。
b）如果它是一個無效的單元格，就像您在方法中編寫的那樣isValid，您需要返回Integer.MIN_VALUE，因為您的其他單元格中可能有負值，并且您希望它們為最大值。
所以你的getMax函數需要是：
public static int getMax(int [][] grid,int row,int col){
? ? if (isTopRight(grid,row,col)) {
? ? ? ?return grid[row][col];
? ? } else if (!isValid(grid,row,col)){
? ? ? ? return Integer.MIN_VALUE;
? ? } else {
? ? ? ? return grid[row][col] + Math.max(getMax(grid,row-1,col),getMax(grid,row,col+1));
? ? }
}
守著星空守著你
TA貢獻1799條經驗 獲得超8個贊
編輯：回答代碼的編輯版本
新解決方案存在的問題：
int currentSum = grid[row][col];和sum = sum + grid[row][col];總和使用左下角的值進行初始化，并在初始調用中
getMax()再次添加相同的值。這不應該是這樣的?？偤蛷?0 開始，加法將通過 完成getMax()。if((isTopRight(grid,row,col)) || (!isValid(grid,row,col)))然后return sum;對于無效位置，這將起作用（請參閱我的代碼下面的限制），但不適用于右上角（因為我們尚未添加角的值）。因此，將這兩個條件分開，只直接返回無效位置。在任何其他位置，首先添加值，然后，如果達到“目標”，則返回總和。否則返回“向右”和“向上”的最大值（遞歸調用現在是正確的）。
解決這些問題并實現您的示例，我得出了以下代碼：
public class Pathfinder {
public static void main(String... args) {
int [][] grid = {
{0,0,0,2,5},
{0,0,0,1,5},
{0,1,1,1,1},
{2,0,0,0,0}
};
System.out.println(getPathMaxSum(grid));
}
public static int getPathMaxSum(int[][] grid) {
int row = grid.length - 1;
int col = 0;
return getMax(grid, 0, row, col);
}
public static int getMax(int[][] grid, int sum, int row, int col) {
if(!isValid(grid, row, col))
return sum;
sum = sum + grid[row][col];
if(isTopRight(grid, row, col))
return sum;
return Math.max(getMax(grid, sum, row - 1, col), getMax(grid, sum, row, col + 1));
}
public static boolean isTopRight(int[][] grid, int row, int col) {
return row == 0 && col == grid[row].length - 1;
}
public static boolean isValid(int[][] grid, int row, int col) {
return (row >= 0 && row < grid.length) && (col >= 0 && col < grid[row].length);
}
}
請注意，如果所有條目均為非負數，則此版本將適用于任何網格（只要堆棧足夠大并且我們不處理太大的數字，例如我們不會得到任何整數溢出）。無論如何，可以通過以下方式操作具有負條目的網格，即通過該算法找到最佳路徑，并且可以輕松地將解決方案“翻譯”回原始網格（只需從每個條目中減去最小值）。
原始代碼的答案
我發現您的代碼存在多個問題：
isValid(grid,row+1,col)和sum1 = grid[row+1][col];您正在嘗試向該行添加
int row = grid.length-1;1，但您（正確地）從 開始。加 1 會給你一個無效的位置，因此第一個分支將永遠不會被執行。相反，您需要從該行中減去1 才能“向上”。sum = sum + Math.max(sum1,sum2);這會改變
sum，但你看不到你移動的方向。然后緊接著...getMax(grid,sum,row+1,col);和getMax(grid,sum,row,col+1);...您使用新的最大總和進行遞歸調用，但從兩個位置進行。為了獲得正確的解決方案，您應該使用它們所代表的值來調用它們。另請注意，此處也
row+1需要替換它。row-1return sum;您現在返回這個最大總和，但完全忽略遞歸調用的返回。相反，您應該比較它們的回報并為自己回報兩者的較高價值。
回溯法與動態規劃
您的算法應該可以正常工作，并且足以解決問題的小實例，但不適用于較大的問題（因為它將為每個步驟進行 2 次遞歸調用，并且您有 2*(n-1) 步驟..導致指數運行時間） 。二次運行時間的另一種方法是向后遍歷該字段，并通過僅向右或向上查看一個字段并將當前字段的值添加到該字段的最大值來選擇最佳方式。只需從右上角開始并向左走，從右到左逐行即可。
添加回答
舉報
0/150
提交
取消