记忆化递归 50分求助

an_yu @ 2022-09-30 21:54:14

#include <iostream>
#include <algorithm>
using namespace std;
int h[100][100];
int res[100][100];
int ski(int r,int c,int r0,int c0){//r,c为起点，最多的方法数
    if(res[r][c]!=-1){//证明已经计算过了
        return res[r][c];
    }else{
        res[r][c]=1;
        //找到上下左右中最大的元素的位置
        int rm=-1;
        if(c-1>=0&&h[r][c-1]<h[r][c]){//可行路线
            rm=1;
            ski(r,c-1,r0,c0);
        }
        if(c<c0-1&&h[r][c+1]<h[r][c]){//可行路线
            rm=1;
            ski(r,c+1,r0,c0);
        }
        if(r-1>=0&&h[r-1][c]<h[r][c]){//可行路线
            rm=1;
            ski(r-1,c,r0,c0);
        }
        if(r<r0-1&&h[r+1][c]<h[r][c]){//可行路线
            rm=1;
            ski(r+1,c,r0,c0);
        }
        if(rm==-1){//周围没有比他还要小的
            return res[r][c];
        }else{//在某个位置找到了比它更小的
            res[r][c]+=max(max(res[r-1][c],res[r+1][c]),max(res[r][c+1],res[r][c-1]));  
            return res[r][c];
        }
    }   
}
int main(){
    int r,c,i,j;
    scanf("%d %d",&r,&c);   
    for(i=0;i<r;i++){
        for(j=0;j<c;j++){
            scanf("%d",&h[i][j]);
        }
    }
    for(i=0;i<r;i++){
        for(j=0;j<c;j++){
            res[i][j]=-1;
        }
    }
    int jieguo=1;
    for(i=0;i<r;i++){
        for(j=0;j<c;j++){
            ski(i,j,r,c);
        }
    }   
    for(i=0;i<r;i++){//寻找这个二维数组中的最大值
        int tmp=*max_element(res[i],res[i]+c-1);
        if(tmp>jieguo){
            jieguo=tmp;
        }
    }
    printf("%d",jieguo);
    return 0;
}

by lgy2024 @ 2022-10-01 00:07:06

1:函数改成void; 2:res数组初值可为0，没必要赋值为-1； 3：删掉函数里return后面的值； 4：没必要有rm变量，直接取最大； 5：修改了不必要的else语句； 6：每次搜索需判有无res值； 7：最后取最大时下标有问题，具体见代码

#include <iostream>
#include <algorithm>
using namespace std;
int h[100][100];
int res[100][100];
void ski(int r,int c,int r0,int c0){//r,c为起点，最多的方法数
    if(res[r][c]!=0){//证明已经计算过了
        return;
    }
    res[r][c]=1;
    //找到上下左右中最大的元素的位置
    int maxx=0;
    if(c-1>=0&&h[r][c-1]<h[r][c]){//可行路线
        ski(r,c-1,r0,c0);
        maxx=max(maxx,res[r][c-1]);
    }
    if(c<c0-1&&h[r][c+1]<h[r][c]){//可行路线
        ski(r,c+1,r0,c0);
        maxx=max(maxx,res[r][c+1]);
    }
    if(r-1>=0&&h[r-1][c]<h[r][c]){//可行路线
        ski(r-1,c,r0,c0);
        maxx=max(maxx,res[r-1][c]);
    }
    if(r<r0-1&&h[r+1][c]<h[r][c]){//可行路线
        ski(r+1,c,r0,c0);
        maxx=max(maxx,res[r+1][c]);
    }
    res[r][c]+=maxx;  
}
int main(){
    int r,c,i,j;
    scanf("%d %d",&r,&c);   
    for(i=0;i<r;i++){
        for(j=0;j<c;j++){
            scanf("%d",&h[i][j]);
        }
    }
    int jieguo=1;
    for(i=0;i<r;i++){
        for(j=0;j<c;j++){
            if(res[i][j]==0){
                ski(i,j,r,c);
            }
        }
    }   
    for(i=1;i<=r;i++){//寻找这个二维数组中的最大值
        int tmp=*max_element(res[i],res[i]+c);
        if(tmp>jieguo){
            jieguo=tmp;
        }
    }
    printf("%d",jieguo);
    return 0;
}

by an_yu @ 2022-10-04 16:58:47

@lgy2024 谢谢大佬，太详细了

by an_yu @ 2022-10-04 17:09:16

@lgy2024 您好，您的代码质量比我高太多了hhh。我还有一个问题就是，修改了数组下标那里的错误之后，其他地方不改动可以得到60分。 我觉得其他地方的修改并不影响程序运行结果啊。 剩下的40分是哪里出了问题呢？