himanshu1212's blog

By himanshu1212, history, 7 weeks ago, In English

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

 
 
 
 
  • Vote: I like it
  • -25
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

cAN ANYONE PLEASE SEND THE CODE?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I guess you are right! Could you please give a hint?

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Spoiler
        Spoiler
        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yeah, generally transitions going in both directions can be an issues in DP. But I think you can:

            Spoiler
  • »
    »
    10 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it
#include <iostream>
#include<climits>
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<n;i++)
	{
	    dp[i] = min(dp[i],dp[i+1]+arr[i+1]); //1 step backward
	    dp[i+2] = dp[i]+arr[i];         //2 step forward
	}
	
	cout<<dp[n];
	return 0;
}