Minimum Jumps requires to reach nth stair- Memoization + Tabulation + Space Optimization Solution

Is your feature request related to a problem? Please describe. Yes ! Problem statement :- There is a frog on the '1st' step of an 'N' stairs long staircase. The frog wants to reach the 'Nth' stair. 'HEIGHT [i]' is the height of the '(i+ 1)th' stair.If Frog jumps from 'ith' to 'jth' stair, the energy lost in the jump is given by absolute value of abs( HEIGHT(i-1)] - HEIGHT(j-1)] ). If the Frog is on 'ith' staircase, he can jump either to (i+ 1)th' stair or to '(i+2)th' stair. Your task is to find the minimum total energy used by the frog to reach from '1st' stair to 'Nth' stair.

Describe the solution you'd like Used Memoization + Tabulation + Space Optimization Using DP

` // Memoization TC O(n) , SC O(n) dp array + O(n) stack-space int helper(int n , vector&dp,vector &heights){ if(n == 0) return 0; int left = helper(n-1 , dp , heights) + abs(heights[n] - heights[n-1]); int right = 0; if(n > 1) right = helper(n-2, dp , heights) + abs(heights[n] - heights[n-2]); else right = INT8MAX; if(dp[n] != -1) return dp[n]; else return dp[n] = min(left , right); } int frogJump(int n, vector &heights){ vectordp(n+1 , -1); dp[0] = 0; return helper(n-1 , dp , heights); }

// Tabulation TC O(n) , SC O(n) dp array int frogJump(int n, vector &heights){ vectordp(n+1 , -1); dp[0] = 0; dp[1] = abs(heights[1] - heights[0]);

for(int i = 2; i<n; i++){
    int n_1 = dp[i-1] + abs(heights[i] - heights[i-1]);
    int n_2 = dp[i-2] + abs(heights[i] - heights[i-2]);
    dp[i] = min(n_1 , n_2);
}
return dp[n-1];

}

// Space Optimization TC O(n) , SC O(1) int frogJump2(int n, vector &heights){ vectordp(n+1 , -1); int prev2 = 0; int prev1 = abs(heights[1] - heights[0]);

for(int i = 2; i<n; i++){
    int n_1 = prev1 + abs(heights[i] - heights[i-1]);
    int n_2 = prev2 + abs(heights[i] - heights[i-2]);
    int curr = min(n_1 , n_2);
    prev2 = prev1;
    prev1 = curr;
}
return prev1;

} `

Kumar-laxmi / Algorithms

Minimum Jumps requires to reach nth stair- Memoization + Tabulation + Space Optimization Solution #1673