遞歸中函數的很多調用

我正在使用遞歸實現maxPathSum函數，並且我不知道在函數中使用兩個調用時會發生什麼.i知道那麼稱爲二進制遞歸，並知道如何從此考慮它關於這個問題的答覆 Understanding double recursion 遞歸中函數的很多調用

，但是當我寫的代碼它並沒有給我正確的答案 [注意]唯一需要的方向是對的，下

#include <iostream> 
#include<algorithm> 
using namespace std; 
const int MAX=3; 
int grid[MAX][MAX]={ 
        {5,1,2}, 
        {6,4,8}, 
        {1,8,9} 
}; 

bool valid(int r, int c);//check not get out grid 
int maxPathSum(int r,int c); 

int main() 
{ 
    int sum=0; 
    for(int i=0;i<MAX;i++) 
    sum += maxPathSum(i,i); 
    cout<<"the sum of the longest path is: "<<sum; 
} 

int maxPathSum(int r,int c){ 
    if(!valid(r,c)) 
     return 1; 

    //Reach the last element in the last right down 
    if(r == MAX-1 && c == MAX-1) 
     return grid[r][c]; 

    int path1=maxPathSum(r,c+1);//Right 
    int path2=maxPathSum(r+1,c);//down 

    return grid[r][c]+max(path1,path2); 
} 

bool valid(int r, int c){ 
    if(r > MAX-1) 
     return false; 
    if(c > MAX-1) 
     return false; 

    return true; 
}

當我打電話功能主要沒有循環有時它給我r飛行回答

這樣低的矩陣長度

const int MAX=2; 
int grid[MAX][MAX]={ 
        {5,2}, 
        {1,8} 
}; 
maxPathSum(0,0);

來源

2017-07-09 Ahmed fouad

'if（！valid（r，c））return 1;'這個情況不應該是'return 0'嗎？ – Arcinde

歡迎來到StackOverflow。請閱讀並遵守幫助文檔中的發佈準則。 [最小，完整，可驗證的示例]（http://stackoverflow.com/help/mcve）適用於此處。特別是，包括您的問題情況的實際和預期產量。 – Prune

你正在一個雙總和。

return grid[r][c]+max(path1,path2)

這段代碼已將路徑上的元素相加。

for(int i=0;i<MAX;i++) 
sum += maxPathSum(i,i);

maxPathSum將返回（i，i）和（2,2）之間路徑上所有元素的總和。那麼sum將包含對角元素上所有這些和的總和。我不認爲你想要那樣。

在main中調用maxPathSum（0,0）應該給出答案。

現在讓我們說你調用maxPathSum（1,2）。這個函數將調用maxPathSum（2,2）和maxPathSum（1,3）。第一個將返回e22和後一個。如果e22 = 0，結果將不正確。

我回答這個問題尋找（0,0）之間的最大路徑的問題（MAX-1，MAX-1）。如果問題沒有像這樣定義，則應該明確指定它。

來源

2017-07-09 08:20:00 SugarOnBacon

遞歸中函數的很多調用

回答

相關問題