动态规划的引入 P1434 [SHOI2002]滑雪【DFS+记忆化搜索】 题目 题目分析 代码
https://www.luogu.com.cn/problem/P1434
题目分析
使用DFS来进行遍历，一个节点查看自己的上下左右四个方向，如果存在比自己小的就可以进入进行DFS
但是可能存在某个节点重复查询的问题，那么就需要使用动态规划中的记忆化搜索（如果该节点已经在之前进行了搜索就直接使用dp数组中的长度，不再进行递归）
代码
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; int dp[211][211]; int list[211][211]; int dx[4] = { 0,0,1,-1 };//用来表示方向 int dy[4] = { 1,-1,0,0 }; int n, m; int dfs(int x, int y) { if (dp[x][y])return dp[x][y]; dp[x][y]=1; for (int i = 0; i < 4; i++) { int xx = dx[i]+x; int yy = dy[i]+y; if (xx >= 0 && xx < n&&yy >= 0 && yy < m&&list[xx][yy] < list[x][y]) { dfs(xx, yy); dp[x][y] = max(dp[x][y], dp[xx][yy] + 1); } } return dp[x][y]; } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%d", &list[i][j]); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) dfs(i, j); int maxx = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (maxx<dfs(i, j))maxx = dp[i][j]; printf("%d", maxx); }