與記憶化

動態規劃由於我是新來的動態規劃。有人可以幫助我實現算法的記憶技術以解決以下問題。與記憶化

有N行和M列的2D矩陣。行從上到下從0到N-1，從左到右從0到M-1。你站在（0,0）。

從，A [i] [j]就可以移動到第[i + 1] [j]的如果A [1 + 1] [j]的> A [i] [j]。或者，如果A [i] [j + 1]> A [i] [j]，則可以將A [i] [j]移動到A [i] [j + 1]。

從（0,0）移動，那是什麼，你可以旅行的最長路徑？

static int a[][],n,m; 
static int find(int x,int y) 
{ 
    if((x==n-1 && y==m-1)) 
    { 
     return 1; 
    } 
    else if(x<n-1 && y<m-1 && a[x+1][y]>a[x][y] && a[x][y+1]>a[x][y]) 
    { 
     return Math.max(find(x+1,y),find(x,y+1))+1; 
    } 
    else if(x<n-1 && a[x+1][y]>a[x][y]) 
    { 
     return find(x+1,y)+1; 
    } 
    else if(y<m-1 && a[x][y+1]>a[x][y]) 
    { 
     return find(x,y+1)+1; 
    } 
    return 1; 
}

其中.. x和y是初始位置（即（0,0））， n和m是行和列resply，一個是實際的矩陣。

來源

2017-06-16 bhaskar talla

最長的路徑是M + N - 2我相信。 –

@折速，目標是找到任何方向最長的路徑，而不是去右上角的單元格。 –

我假設你不允許兩次訪問同一個單元格？ –

您想使用記憶化存儲的find()的結果，以便您可以重新使用它們，如果你已經計算出他們已經：

由m陣列（稱之爲memo說吧）的find()功能外聲明另一個n
之前從find()返回，存儲計算結果memo[x][y]
在find（）方法的開始，檢查是否memo[x][y]已經填寫（爲非零）並返回它，如果它有

來源

2017-06-16 10:21:24

我試過這種技術，但它沒有沒有工作 –

因此，將您的代碼添加到您的答案中，並告訴我們它是如何工作的。 –

它給出了相同的答案，具有相同的時間和空間複雜度 –

回答

相關問題