Could anyone please send the code for this problem?
You are given an array of N integers. You have to find the minimum cost that is required to cross the array by jumping from one element to another. You need to start from the first element of the array and you can jump in both directions,but length of forward jump must be 2 and backward jump must be 1.
The cost of forward and backward jump is the value of the element from which you are jumping.,that is the cost of jumping from i index to (i+2) and the cost of jumping from i to (i-1) index is the value of i element of the array
If you are at the last element then you can jump out of the array and cost of that jump will be the value of the last element of array A
cAN ANYONE PLEASE SEND THE CODE?
I can understand asking for help or hints, but just asking for someone to solve the entire problem for you seems either very suspicious or very lazy.
I'll give you the benefit of the doubt and assume that I'm interpreting things harshly. If you would like help with this problem, I'm sure plenty of people in this community would be happy to help. But you can't post a problem and expect somebody to hand you the answer.
I guess you are right! Could you please give a hint?
Use DP.
The state is the index you are currently at and the transition is the forward and backward jumps.
I can't see any way to have both backward and forward transitions without a Djikstra-esque shortest distance. Can you give an idea on how to know the DAG for this kind of DP? Here, I mean the dependency order in which to calculate.
Yeah, generally transitions going in both directions can be an issues in DP. But I think you can:
observe that it is never optimal to go backwards twice in a row since jumping forward again will just land you back where you started. So you can convert the backwards transition into a forward transition with a cost of A[i] + A[i-1].
Please see if it's correct. I have used memoization.
Gives wrong ans: check for this case 5 5 1 2 10 100