题目地址：http://poj.org/problem?id=1088
问题描述：一个区域由一个二维数组给出。数组的每个数字代表点的高度h，0<=h<=10000。行数R和列数C(1 <= R,C <= 100)。
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
在这个数组中，一个人从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。求最长的滑雪路径。
解题思路：每个数据都存储在这一个二维数组RC[][]中，针对每个点，人可以选择从上下左右四个方向进行滑雪，但这个点必须存在而且比中心点小。那么假设人此时在（i，j）处，此时四个方向上的路径长度分别为dp[i-1][j],dp[i+1][j],dp[i][j-1],dp[i][j+1]。那么在（i，j）处的路径长度就为dp[i][j]。
因为要求一条最长的路径，那么我们从这四个方向上的dp值中选择最大的，再加上1，即为当前最长的路径。显然，这是一个DP问题。转换方程为
dp[i][j] = max(dp[i-1][j],dp[i+1][j],dp[i][j-1],dp[i][j+1])+1
当dp[i][j]所在的（i，j）处的数组值RC[i][j]为数组最小值时，此时dp[i][j] = 0
运行一组数据，截图如下。
网友评论