A frog wants to climb a staircase with n steps. Given an integer array heights, where heights[i] contains the height of the i****th step.
To jump from the i****th step to the j****th step, the frog requires abs(heights[i] - heights[j]) energy, where abs() denotes the absolute difference. The frog can jump from any step either one or two steps, provided it exists. Return the minimum amount of energy required by the frog to go from the 0****th step to the **(n-1)**th step.
Examples:
Input: heights = [2, 1, 3, 5, 4]
Output: 2
Explanation: One possible route can be,
0th step -> 2nd Step = abs(2 - 3) = 1
2nd step -> 4th step = abs(3 - 4) = 1
Total = 1 + 1 = 2.
Input: heights = [7, 5, 1, 2, 6]
Output: 9
Explanation: One possible route can be,
0th step -> 1st Step = abs(7 - 5) = 2
1st step -> 3rd step = abs(5 - 2) = 3
3rd step -> 4th step = abs(2 - 6) = 4
Total = 2 + 3 + 4 = 9.
Constraints:
1 <= n <= 104
0 <= heights[i] <= 104
Approach - Bottom Up tabulation space optimized
- Go bottom up we have prev2,prev1 so for iteration we calculate these 2 and then update current is with prev1 as that is in front and at the end we return the same
- O(n), O(1)
class Solution {
public int frogJump(int[] heights) {
int prev1 = 0, prev2 = 0;
for (int i = 1; i < heights.length; i++) {
int jump1 = prev1 + Math.abs(heights[i] - heights[i-1]);
int jump2 = Integer.MAX_VALUE;
if (i > 1 ) {
jump2 = prev2 + Math.abs(heights[i] - heights[i-2]);
}
int curr = Math.min(jump1, jump2);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
}