Dynamic Programming

,
1

You are given an array. You have to find the minimum cost that is required to cross the array by jumping from one element to another. The length of the forward jump must be two and backward jump one and the cost of the jump is the value of the element from which you are jumping.

I have applied like

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

int MinCost(int cost[],int n,int dp[],int ind){
	if(ind<0)
		 return INT_MAX;
    if(ind>n-1)
    	 return 0;

    if(dp[ind]!=-1)
    	 return dp[ind];
    dp[ind]=min(cost[ind-2]+MinCost(cost,n,dp,ind-2),cost[ind+1]+MinCost(cost,n,dp,ind+1));
    return dp[ind];


}

int main() { 
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
    	cin>>arr[i];
    int dp[n];
    memset(dp,-1,sizeof(dp));
    dp[0]=arr[1];
    dp[1]=1;
   int result= MinCost(arr,n,dp,n-1);     //i am passing n-1 cause i need to reach at (n-1)th index
   cout<<result<<"\n";
   return 0;
}

i Don’t know why this code is failing i used memoization and recursion. someone please help.

2

try to initialize dp with INT_MAX

3

didn’ work out .

4

if ind>n-1
return INT_MAX
because of your assumption that you start solving with ind as n-1

1 Like