蓝桥杯备战——Day 5 滑雪

链接

这是一道相对来说比较难的dp题了（对我来说） 我的思路是： 因为这些数字的大小是无规律的，因此，我们需要找到从每一个点出发，所能走过的最大的路经长度
这个显然要用到递归
然而如果每个点都按照上下左右这样来递归探寻，最坏时间复杂度为O(mn的mn次方)(不知道是不是这么算的，我把常数去掉了)
这样肯定会超时 因此我们需要用dp来记录：假设这个点具有dp值，那么说明它已经被搜寻过并且该点的最大路径值就是dp值，我们可以直接用

```cpp
#include
#include
using namespace std;
int R,C;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int a[102][102],dp[102][102];//dp等于0表明dp数组未更新 //一开始这里出现了一个错误：我写了dp[102][102]={-1}
							//错误在于：二维数组不能直接整体赋值，应该给每一个元素赋值 
int ans=0;
int func(int x,int y){
	//从x,y点出发 
	if(dp[x][y]!=0)
		return dp[x][y];//如果dp值不为空，直接使用 
	dp[x][y]=1;//此时再对dp里某一点赋值，因为这需要在后面计算步数时候使用 
	//如果不是，就得搜寻了 
	//遍历四种情况，这里可以模仿上次的过河卒，用数组表示前进的方位然后用for遍历
	//x的范围是[1,R]；y的范围是[1,C]
	for(int i=0;i<4;i++){
		int xx=x+dx[i],yy=y+dy[i];//下面一步要走的 
		if(xx>=1&&xx<=R&&yy>=1&&yy<=C&&a[xx][yy]>R>>C; 
	for(int i=1;i<=R;i++){
		for(int j=1;j<=C;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=R;i++){
		for(int j=1;j<=C;j++){
			func(i,j);
		}
	}
	for(int i=1;i<=R;i++){
		for(int j=1;j<=C;j++){
			if(dp[i][j]>=ans)
				ans=dp[i][j];		
		}
	}
	cout< 
复盘 
 
 
一、
 刚开始不知道如何在递归中计算步数。因为上一个点的dp值就是max（1+走到的那个点的dp值，当前该点的dp值），而我一开始就将dp数组初始化（一种类似于bool的初始化），这样就导致了我不知道如何去更新dp值。
 如代码中写的一样，在判断是否已经有了dp值之后在进行步数上的赋值if(dp[x][y]!=0) return dp[x][y]; dp[x][y]=1;
 其实，一旦走到这个点，就会有dp值的更新，那么既然我们已经判断了某个位置暂时没有dp值，那么就可以给他初始化为1，因为任何地方走过来步数都为1（但是这个1应该只会在滑雪到了末尾的时候才会使用）
 二、
 别忘记了dp[x][y]=max(dp[x][y],dp[xx][yy]+1);这个更新