[DP]根据数组中定义的跳跃力求一个人可以跳跃的最大距离

发布于 2025-01-11 13:42:32 字数 758 浏览 0 评论 0原文

我有一个人从我们空间的最左边部分开始，我们有两个数组第一个数组 = [p1,p2,p3,p4,p5,....,pn] 数组的每个元素表示平台距人可以跳跃的起点的距离。第二个数组 =[d1,d2,d3,d4,d5,....,dn] 该数组的每个 i 元素存储一个人在爬上 i 个平台时会跳跃的距离。现在，对于每个平台，他是否想要爬上并跳跃或者想要绕过它取决于人。跳跃后，他不必落在某个平台上，他也可以落在两个平台之间。最后，我们希望最大化他能够跳跃的距离，我们不在乎他走了多远：- 我正在尝试一个DP解决方案，

我尝试了这个问题，但只能得到一个递归的想法，我认为我可以递归地检查所有可能的路径并找到总距离的最大值，但这将具有相当高的时间复杂度对于更大的输入会失败。如果有人能给出 O(n^3) 或 O(n^2) 解决方案的提示，我将不胜感激。

澄清问题的示例

假设平台数组是 [1,4,7,10,11] 这意味着平台位于距平台 1m、4m、7m、11m、12m 处。现在假设跳跃距离数组为 [2,3,5,1,10] 现在，当他开始时，他可以爬上平台 1 或继续行走并前往下一个平台，如果他爬上平台 1，他可以跳跃 2m，这将添加到他的跳跃距离中跳了 2m 后，他在 3m 处跌落，现在我们再次开始行走，现在可以决定爬上 4m 处的第二个平台，然后从第二个平台跳 3m，他的跳跃将在第三个平台上结束，从那里他可以决定爬下来并行走或者根据跳跃距离数组再次跳跃。在这里，如果我们步行到下一个平台，那就更有利了，因为从第 5 个平台开始，他可以立即跳跃 10m。最后我们要通过遍历整个数组来找到他跳跃所能走的最大距离。这里他可以跳跃的最大距离是 16

原文

I have a person who starts from the left-most part in our space and we are given two arrays
First Array = [p1,p2,p3,p4,p5,....,pn] each element of the array indicates the distance of the platform from a starting point where the person can do his jump.
Second array =[d1,d2,d3,d4,d5,....,dn] each ith element of this array stores the distance person will jump if he climb on ith platform.
Now for each platform it is upon the person whether he want to climb it and take the jump or he want to bypass it. After taking the jump it is not necessary he falls on some platform only he can fall between two platforms also.
In the end we want to maximise the distance he is able to jump we don't care what distance he has walked:-
I am trying for a DP solution for the same

I tried the problem but could only get to a recursive idea where I thought I can check for all possible paths recursively and find the maximum of total distance but that would have a pretty high time complexity which would fail for larger inputs.
I would be thankful if someone can give a hint of O(n^3) or O(n^2) solution.

Example to clarify the problem

Suppose the platforms array is [1,4,7,10,11]
which means platforms are located 1m, 4m ,7m ,11m, 12m from the platform.
Now suppose the jumping distance array is [2,3,5,1,10]
Now when he starts he can either climb on platform 1 or keep walking and go to next platform if he climbs on platform 1 he can jump 2m which would be added to his jumping distance
after jumping 2m he falls at 3m mark now we again starts walking and can now decide to climb 2nd platform which is at 4m and jump 3m from the second platform and his jump would end on 3rd platform from where he can decide to climb down and walk or again jump according to jumping distance array.
Here if we walk to next platforms it would be more beneficial as from 5th platform he can jump 10m at once.
In the end we have to find the maximum distance which he can cover by jumping by traversing through the complete array.
Here the maximum distance which he can jump would be 16

分享到QQ

分享到微博