为什么遍历最大值用不能用dp[i][j]

P1434 [SHOI2002] 滑雪

fufuQAQ @ 2022-04-08 10:27:57

cpp
#include<bits/stdc++.h>
using namespace std;
int m,n,maxn;
int a[110][110],dp[110][110];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

int dfs(int x,int y)//从1,1开始    //错误点dfs 
{
    if(x<1 || x>m || y<1 || y>n)   return 0;
    if(dp[x][y]!=0)   return dp[x][y];
//  if(dp[x][y]!=0)  return dp[x][y];    //注意点:记忆化搜索别忘了,这题卡空间和时间 
    dp[x][y]=1;  //错误点1;初始化为1别漏掉,经过自己这个点长度为1 
    for(int i=0;i<4;i++)
    {
        int xx=dir[i][0]+x;
        int yy=dir[i][1]+y;     
        if(x>=1 && x<=m && y>=1 && y<=n && a[x][y] > a[xx][yy])
        {
            dfs(xx,yy);
            dp[x][y]=max(dp[x][y],dp[xx][yy]+1);
        }
    }
    return dp[x][y];//错误点2:函数最后没有返回值,要不然后面算的dp[x][y]就不会返回到函数里面去 
}

int main()
{
    cin>>m>>n;
    for(int i=1;i<=m;i++)//m行 
        for(int j=1;j<=n;j++)//n列 
            cin>>a[i][j];

    for(int i=1;i<=m;i++)//m行 
    {
        for(int j=1;j<=n;j++)//n列 
            cout<<dp[i][j]<<" ";
        cout<<endl;
    }

    for(int i=1;i<=m;i++)//m行 
        for(int j=1;j<=n;j++)//n列
//          maxn=max(maxn,dfs(i,j));
            maxn=max(maxn,dp[i][j]);

    cout<<maxn<<endl;
    return 0;         
}

by DarksideCoderω @ 2022-04-08 10:33:49

你的Dfs还没有更新,跑一遍dfs才能用


by fufuQAQ @ 2022-04-08 10:41:04

@DarksideCoderω 好的,谢谢


|