A frog wants to climb a staircase with n steps. Given an integer array heights, where heights[i] contains the height of the ith step, and an integer k.
To jump from the ith step to the jth step, the frog requires abs(heights[i] - heights[j]) energy, where abs() denotes the absolute difference. The frog can jump from the ith step to any step in the range [i + 1, i + k], provided it exists. Return the minimum amount of energy required by the frog to go from the 0th step to the (n-1)th step.
Examples:
Input: heights = [10, 5, 20, 0, 15], k = 2
Output: 15
Explanation:
0th step -> 2nd step, cost = abs(10 - 20) = 10
2nd step -> 4th step, cost = abs(20 - 15) = 5
Total cost = 10 + 5 = 15.
Input: heights = [15, 4, 1, 14, 15], k = 3
Output: 2
Explanation:
0th step -> 3rd step, cost = abs(15 - 14) = 1
3rd step -> 4th step, cost = abs(14 - 15) = 1
Total cost = 1 + 1 = 2.
Constraints:
- 1 <= n <= 104
- 1 <= k <= 10
- 0 <= heights[i] <= 104
Approach - Tabulation with space
- Bottom up we need another loop to check each jump and find the min and store in dp
O(n*k), O(n)
class Solution {
public int frogJump(int[] heights, int k) {
int[] dp = new int[heights.length];
Arrays.fill(dp, Integer.MAX_VALUE);
//base case standard aka bottom
dp[0] = 0;
//we start with 1 always
for (int i = 1; i < heights.length; i++) {
for (int j = 1; j <= k; j++) {
if (i - j >= 0) { // so that i - j is not out of bounds
int jump = dp[i-j] + Math.abs(heights[i] - heights[i-j]);
dp[i] = Math.min(dp[i], jump);
}
}
}
//The up will have the result
return dp[heights.length - 1];
}
}