question summary
The problem asks us to compute the minimum total cost it takes for a frog to travel from stone $$$1$$$ to stone $$$N (N \le 10^5)$$$ given that the frog can only jump a distance of one or two. The cost to travel between any two stones $$$i$$$ and
$$$j$$$ is given by $$$|h_i - h_j|$$$ , where $$$h_i$$$ represents the height of stone $$$i$$$ .
MY CODE
#include<bits/stdc++.h>
typedef long long ll;
#define mod 1000000007
#define loop(i,a,b) for(int i= (a);i <(b) ; i++)
using namespace std ;
int solve(ll arr[], ll s, ll e, vector<vector<ll>> &dp)
{
if(dp[s][e] != -1) //THIS STORES COST TO GO FROM S TO E
return dp[s][e];
else
{
if(s==e)
return dp[s][e] = 0;
else if(s+1 == e)
return dp[s][e] = abs(arr[e]- arr[s]);
else if(s+2 == e)
return dp[s][e] = min(abs(arr[s+1]-arr[e])+ abs(arr[s]-arr[s+1]), abs(arr[s]-arr[e]));
else if(s+2<e)
return dp[s][e] = min(solve(arr,s+1,e,dp)+abs(arr[s]-arr[s+1]), solve(arr,s+2,e,dp)+abs(arr[s]-arr[s+2]) );
}
}
int main()
{
ios_base::sync_with_stdio (false);
cin.tie(NULL);
ll n;
cin>>n;
ll arr[n];
loop(i,0,n)
cin>>arr[i];
vector<vector<ll>> dp (n+1, vector<ll>(n+1, -1));
cout<<solve(arr,0,n-1,dp);
return 0;
}
MY CODE PASSES HALF TEST CASES AND FAILS HALF BECAUSE OF RUNTIME ERROR . WHAT MISTAKE HAVE I DONE ?
The space complexity for your solution is O(n^2). So, for test cases with n > 1000 your solution is exceeding the memory limit. In general you can create an integer array of size ~ 1e6. Try coming up with a solution having Space Complexity O(n) or O(nlogn).