推销一下：
算法提高课第一章动态规划全题解（正在完善）算法提高课第一章动态规划全题解（正在完善）
题目描述
给定一个 RR 行 CC 列的矩阵，表示一个矩形网格滑雪场。
矩阵中第 ii 行第 jj 列的点表示滑雪场的第 ii 行第 jj 列区域的高度。
一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。
当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
下面给出一个矩阵作为例子：
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
在给定矩阵中，一条可行的滑行轨迹为 24−17−2−124−17−2−1。
在给定矩阵中，最长的滑行轨迹为 25−24−23−…−3−2−125−24−23−…−3−2−1，沿途共经过 2525 个区域。
现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。
输入格式
第一行包含两个整数 RR 和 CC。
接下来 RR 行，每行包含 CC 个整数，表示完整的二维矩阵。
输出格式
输出一个整数，表示可完成的最长滑雪长度。
数据范围
1≤R,C≤3001≤R,C≤300,
0≤矩阵中整数≤100000≤矩阵中整数≤10000
输入样例：
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
输出样例：
25
梳理一下题目含义：
给定一个RR 行 CC 列的矩形网格滑雪场
一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。
当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
注意：
那个人可以从矩形网格滑雪场的任意一点出发
可以上下左右移动
每次只能滑一个单位距离
这个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度
解释一下样例：
看懂了题目，现在我们来看看样例输出为什么是2525。
如图：
字丑了点QWQ，不管它了，继续！
算法1
(动态规划) O(n2)O(n2)
这道题用dfs肯定会超时，毕竟题目已经明确指出这道题是动态规划问题
所以我们这道题可以用动态规划做。
DPDP分析图如图：
讲解一下状态计算的部分：
如图：
时间复杂度
参考文献
C++ 代码
#include #include #include using namespace std; const int N = 310; int n,m; //网格滑雪场的行和列 int f[N][N]; //状态转移式 int h[N][N]; //网格滑雪场 int dx[4] = {-1,0,1,0}; int dy[4] = {0,1,0,-1}; int dp(int x,int y){ int &v = f[x][y]; //Y总说的小技巧，等于把f[x][y]简化成了v，如果v发生变化，f[x][y]也会随之变化 if(v != -1) return v; //如果已经计算过了，就可以直接返回答案 v = 1; //注意v要先赋值为1哦~ for(int i = 0;i < 4;i ++){ //四个方向 int xx = x + dx[i]; int yy = y + dy[i]; if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && h[x][y] > h[xx][yy]){ //判断这点是否能走 v = max(v,dp(xx,yy) + 1); //更新 } } return v; //别忘了返回v啊（被坑了 } int main(){ cin>>n>>m; //输入滑雪场行和列 for(int i = 1;i <= n;i ++){ for(int j = 1;j <= m;j ++){ cin>>h[i][j]; //读入滑雪场数据 } } memset(f,-1,sizeof f); int res = 0; //最后答案 for(int i = 1;i <= n;i ++){ for(int j = 1;j <= m;j ++){ //因为这个人可以在任意一点开始滑，所以要遍历一遍滑雪场 res = max(res,dp(i,j)); //更新答案 } } cout<<res<<endl; return 0; }
注意：
要记得把ff数组初始化为−1−1
定义vv的时候注意要加上&&
如果这个点没计算过，vv记得要赋值为11
v=max(v,dp(xx,yy)+1)v=max(v,dp(xx,yy)+1) 不要忘了 +1+1
记得要返回v
