### himanshu1212's blog

By himanshu1212, history, 7 weeks ago,

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

• -25

 » 7 weeks ago, # |   -8 cAN ANYONE PLEASE SEND THE CODE?
•  » » 7 weeks ago, # ^ |   +3 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.
•  » » » 7 weeks ago, # ^ |   0 I guess you are right! Could you please give a hint?
•  » » » » 7 weeks ago, # ^ |   0 SpoilerUse DP. SpoilerThe state is the index you are currently at and the transition is the forward and backward jumps.
•  » » » » » 7 weeks ago, # ^ |   0 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.
•  » » » » » » 7 weeks ago, # ^ |   0 Yeah, generally transitions going in both directions can be an issues in DP. But I think you can: Spoilerobserve 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].
•  » » 10 days ago, # ^ | ← Rev. 2 →   0 import math n=int(input()) c=list(map(int,input().split())) cost=[0] for i in range(n): cost.append(c[i]) dp=[math.inf]*(n+3) dp[1]=0 dp[3]=cost[1] dp[2]=dp[3]+cost[3] for i in range(4,n+3): dp[i]=min(dp[i-2]+cost[i-2],dp[i]) print(dp) print(min(dp[n+1],dp[n+2]))Is this Correct?
 » 6 days ago, # |   0 #include #include using namespace std; int main() { int n=5; int arr[n] = {1,2,3,4,100} ; int dp[n+1]; for(int i=0;i<=n;i++) { dp[i]=INT_MAX; } dp[0]=0; dp[2]=arr[0]; //2 step forward for(int i=1;i