背景 我今天接受了一次采訪，被問到以下問題。給你一個(gè)網(wǎng)格。 int [][] grid = { {0,0,0,2,5}, {0,0,0,1,5}, {0,1,1,1,1}, {2,0,0,0,0} };您從網(wǎng)格的左下角開始。你只能向上和向右。這個(gè)想法是到達(dá)右上角。你要走一條能給你帶來最大價(jià)值的道路。上面的輸出是 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);}我正在嘗試遞歸地解決這個(gè)問題。我認(rèn)為我在每個(gè)位置都有 2 個(gè)可能的選擇，并且我想獲得這兩個(gè)選擇中的最大值，但由于某種原因我無法獲得正確的輸出。我有兩個(gè)輔助函數(shù)，它們檢查我的位置在網(wǎng)格內(nèi)是否有效，以及我是否已經(jīng)點(diǎn)擊了右上角，如果有，那么我就點(diǎn)擊了我的基本情況。我很想知道我哪里出錯(cuò)了。
2 回答
慕桂英546537
TA貢獻(xiàn)1848條經(jīng)驗(yàn) 獲得超10個(gè)贊
sum您的方法中不需要參數(shù)。
我假設(shè)您已經(jīng)了解自上而下的遞歸方法如何解決這個(gè)問題。但同樣為了完整起見，基本公式是：
您從 處的單元格開始row，獲取其值，然后向上或向右col查找。(row-1, col)(row, col+1)
所以結(jié)果將是：
grid[row][col] + Math.max( getMax( row-1, col, grid ), getMax( row, col+1, grid ) )
基本條件：
a）如果它位于右上角，即目的地，則無需遞歸，只需返回該單元格處的值即可。
b）如果它是一個(gè)無效的單元格，就像您在方法中編寫的那樣isValid，您需要返回Integer.MIN_VALUE，因?yàn)槟钠渌麊卧裰锌赡苡胸?fù)值，并且您希望它們?yōu)樽畲笾怠?/p>
所以你的getMax函數(shù)需要是：
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貢獻(xiàn)1799條經(jīng)驗(yàn) 獲得超8個(gè)贊
編輯：回答代碼的編輯版本
新解決方案存在的問題：
int currentSum = grid[row][col];和sum = sum + grid[row][col];總和使用左下角的值進(jìn)行初始化，并在初始調(diào)用中
getMax()再次添加相同的值。這不應(yīng)該是這樣的?？偤蛷?0 開始，加法將通過 完成getMax()。if((isTopRight(grid,row,col)) || (!isValid(grid,row,col)))然后return sum;對(duì)于無效位置，這將起作用（請(qǐng)參閱我的代碼下面的限制），但不適用于右上角（因?yàn)槲覀兩形刺砑咏堑闹担?。因此，將這兩個(gè)條件分開，只直接返回?zé)o效位置。在任何其他位置，首先添加值，然后，如果達(dá)到“目標(biāo)”，則返回總和。否則返回“向右”和“向上”的最大值（遞歸調(diào)用現(xiàn)在是正確的）。
解決這些問題并實(shí)現(xiàn)您的示例，我得出了以下代碼：
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);
}
}
請(qǐng)注意，如果所有條目均為非負(fù)數(shù)，則此版本將適用于任何網(wǎng)格（只要堆棧足夠大并且我們不處理太大的數(shù)字，例如我們不會(huì)得到任何整數(shù)溢出）。無論如何，可以通過以下方式操作具有負(fù)條目的網(wǎng)格，即通過該算法找到最佳路徑，并且可以輕松地將解決方案“翻譯”回原始網(wǎng)格（只需從每個(gè)條目中減去最小值）。
原始代碼的答案
我發(fā)現(xiàn)您的代碼存在多個(gè)問題：
isValid(grid,row+1,col)和sum1 = grid[row+1][col];您正在嘗試向該行添加
int row = grid.length-1;1，但您（正確地）從 開始。加 1 會(huì)給你一個(gè)無效的位置，因此第一個(gè)分支將永遠(yuǎn)不會(huì)被執(zhí)行。相反，您需要從該行中減去1 才能“向上”。sum = sum + Math.max(sum1,sum2);這會(huì)改變
sum，但你看不到你移動(dòng)的方向。然后緊接著...getMax(grid,sum,row+1,col);和getMax(grid,sum,row,col+1);...您使用新的最大總和進(jìn)行遞歸調(diào)用，但從兩個(gè)位置進(jìn)行。為了獲得正確的解決方案，您應(yīng)該使用它們所代表的值來調(diào)用它們。另請(qǐng)注意，此處也
row+1需要替換它。row-1return sum;您現(xiàn)在返回這個(gè)最大總和，但完全忽略遞歸調(diào)用的返回。相反，您應(yīng)該比較它們的回報(bào)并為自己回報(bào)兩者的較高價(jià)值。
回溯法與動(dòng)態(tài)規(guī)劃
您的算法應(yīng)該可以正常工作，并且足以解決問題的小實(shí)例，但不適用于較大的問題（因?yàn)樗鼘槊總€(gè)步驟進(jìn)行 2 次遞歸調(diào)用，并且您有 2*(n-1) 步驟..導(dǎo)致指數(shù)運(yùn)行時(shí)間） 。二次運(yùn)行時(shí)間的另一種方法是向后遍歷該字段，并通過僅向右或向上查看一個(gè)字段并將當(dāng)前字段的值添加到該字段的最大值來選擇最佳方式。只需從右上角開始并向左走，從右到左逐行即可。
添加回答
舉報(bào)
0/150
提交
取消