为什么遍历最大值用不能用dp[i][j]
查看原帖
为什么遍历最大值用不能用dp[i][j]
668320
fufuQAQ楼主2022/4/8 10:27
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;         
}
2022/4/8 10:27
加载中...