【POJ1088】-DP问题之最长路径

题目地址: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

运行一组数据,截图如下。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 动态规划(Dynamic Programming) 本文包括: 动态规划定义 状态转移方程 动态规划算法步骤 最长...
    廖少少阅读 8,654评论 0 18
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 14,349评论 0 33
  • 分治方法 将问题划分成互不相交的子问题 递归地求解子问题 将子问题的解组合起来 动态规划(两个要素:最优子结构、子...
    superlj666阅读 3,468评论 0 0
  • A - 数字三角形题解:假设getMax(i,j)表示点(i,j)到底部的最长路径,那么getMax(i,j)=m...
    Gitfan阅读 4,363评论 0 0
  • Android 自定义View的各种姿势1 Activity的显示之ViewRootImpl详解 Activity...
    passiontim阅读 175,173评论 25 709