himanshu1212's blog

Jump from one array element to another
By himanshu1212, history, 4 years 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

Comments Comments (8)
| Write comment?
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

cAN ANYONE PLEASE SEND THE CODE?

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Spoiler
        Spoiler
        → Reply
        • »
          »
          »
          »
          »
          4 years 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years 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
            → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please see if it's correct. I have used memoization.

#include <bits/stdc++.h>
using namespace std;

static int t[10000]; 
// ...Or any maximum size of the array.

int minCost(vector<int> &A, int pos){
    if(pos > A.size()-1){
        return t[pos] = 0;
    }
    else if(t[pos] != -1){
        return t[pos];
    }
    int c1;
	if(t[pos+2] != -1){
		c1 = t[pos+2];
	}
    else{
		c1 = minCost(A, pos+2) + A[pos];
	}
	
    if(pos>0 && t[pos-1] != -1){
		int c2;
		if(t[pos-1] != -1){
			c2 = t[pos-1];
		}
		else{
        	c2 = minCost(A, pos-1) + A[pos];
		}
        return t[pos] = min(c1, c2);
    }
    else{
        return t[pos] = c1;
    }
}

int main(){
    memset(t, -1, sizeof(t));
    int N;
    cin>>N;
    vector<int> A(N);
 
 	for(int i=0; i<N; i++){
        cin>>A[i];
    }
    cout<<minCost(A, 0);
    return 0;
}
→ Reply