递归中函数的很多调用

我正在使用递归实现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

递归中函数的很多调用

回答

相关问题