'[DP]Finding maximum distance a person can jump according to jumping power defined in array
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
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
