本文主要是介绍1280：【例9.24】滑雪，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【解题思路】
1. 状态定义
状态定义：dp[i][j]：从(i,j)出发的所有路线中，长度最长的路线的长度。
2. 状态转移方程
记第(i,j)位置的高度为a[i][j]。
集合：从(i,j)出发的所有路线
分割集合：根据下一步可以到达的位置分割集合。
下一步可以到达的位置有：(i-1,j), (i+1,j), (i,j-1), (i,j+1)。只要该位置的高度低于当前(i,j)位置的高度，就可以到达这里。
如果a[i-1][j] < a[i][j]，那么下一步可以到(i-1,j)。从(i,j)出发的最长路线长度，为从(i-1,j)出发的最长路线长度再加1，即dp[i][j] = dp[i-1][j] + 1。
如果a[i+1][j] < a[i][j]，那么下一步可以到(i+1,j)。从(i,j)出发的最长路线长度，为从(i+1,j)出发的最长路线长度再加1，即dp[i][j] = dp[i+1][j] + 1。
如果a[i][j-1] < a[i][j]，那么下一步可以到(i,j-1)。从(i,j)出发的最长路线长度，为从(i,j-1)出发的最长路线长度再加1，即dp[i][j] = dp[i][j-1] + 1。
如果a[i][j+1] < a[i][j]，那么下一步可以到(i,j+1)。从(i,j)出发的最长路线长度，为从(i,j+1)出发的最长路线长度再加1，即dp[i][j] = dp[i][j+1] + 1。
以上四种情况求最大值。
由于在求(i,j)时，其上下左右四个位置的状态：dp[i-1][j], dp[i+1][j], dp[i][j-1], dp[i][j+1]并不能确定都已经求出来了。因此可以通过记忆化递归的方法来求解状态。
设函数dfs(i, j)，作用为求解状态dp[i][j]。如果dp[i][j]已经求出来了（值大于0），那么直接返回dp[i][j]。否则通过上述状态转移方程递归求解。
遍历所有的位置，求出从每个位置出发的路线的最长长度，求它们中的最大值，即为该问题的结果。
【题解代码】
#include <iostream>using namespace std;const int N = 105;int n, m, a[N][N], dp[N][N];
int mov[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};bool ok(int x, int y) {return x > 0 && x <= n && y > 0 && y <= m;
}int dfs(int x, int y) { //返回从起点开始最多能滑几步(不包含起点)if (dp[x][y] != 0)return dp[x][y];int maxn = 0;for (int i = 0; i < 4; i ++) {int dx = x + mov[i][0];int dy = y + mov[i][1];if (ok(dx, dy) && a[dx][dy] < a[x][y]) {maxn = max(maxn, dfs(dx, dy));}}return dp[x][y] = maxn + 1;
}int main() {scanf ("%d %d", &n, &m);for (int i = 1; i <= n; i ++)for (int j = 1; j <= m; j ++)scanf ("%d", &a[i][j]);int ans = 0;for (int i = 1; i <= n; i ++)for (int j = 1; j <= m; j ++)ans = max(ans, dfs(i, j));printf ("%d", ans);return 0;
}
这篇关于1280：【例9.24】滑雪的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
