记忆化递归 50分求助
查看原帖
记忆化递归 50分求助
758984
an_yu楼主2022/9/30 21:54
#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;
}

采用的是记忆化递归算法,思路就是递归遍历每一个点的上下左右,但是只有50分。


希望大佬能够给指出错误,另外祝大家国庆节快乐!

2022/9/30 21:54
加载中...