Finding minimum cost to reach the end of array

Question

An array of costs was given. You can either take two jumps forward or one jump backward. If you land on a particular index, you have to add the cost to your total. Find the minimum cost needed to cross the array or reach the end of the array.

Input:

5 (Number of elements in the array)

[9,4,6,8,5] (Array)

1 (Index to start)

Output:

12

Explanation: We start from index 1, jump to 3 and then jump out for a total cost of 8+4=12.

How can we build the DP solution for this?

Answer 1

You can use recursive program with Dp

//cur will the final destination that is last element at first execution
//N is no of elements
int Dp[N]={0};
Dp[0]=element[0]; //initial condition
least_path(cur,*elements,N)
{
   if(cur>N-1 || cur<0)
     return INT_MAX;
  if(Dp[cur])
   return Dp[cur];
  int temp1=least_path(cur-2,*elements,N)+element[cur];
  int temp2=least_path(cur+1,*elements,N)+element[cur];
  Dp[cur]=min(temp1,temp2);
  return Dp[cur];
}