Minimal Cost OR Frog with K distance

Problem Statement:

There are n stones and an array of heights and Geek is standing at stone 1 and can jump to one of the following: Stone i+1, i+2, … i+k stone and cost will be [hi-hj] is incurred, where j is the stone to land on. Find the minimum possible total cost incurred before the Geek reaches Stone n.

Example :

Input: n = 5, k = 3 heights = {10, 30, 40, 50, 20} Output: 30 Explanation: Geek will follow the path 1→2→5, the total cost would be | 10-30| + |30-20| = 30, which is minimum

Example :

Input: n = 3, k = 1 heights = {10,20,10} Output: 20 Explanation: Geek will follow the path 1→2→3, the total cost would be |10 - 20| + |20 - 10| = 20.

Constraint:
$2$ ⇐ $n$ ⇐ 10${}^3$
$1$ ⇐ $k$ ⇐ 100
$1$ ⇐ heights[i] ⇐ 10${}^4$

Solution:

1. Recursion and Memoization

class Solution {
    private int minimizeCostUtil(int arr[], int idx, int k, int[] dp){
        if(idx == arr.length - 1){
            return 0;
        }
        if(idx == arr.length - 2){
            return Math.abs(arr[idx] - arr[idx + 1]);
        }
        if(dp[idx] != -1){
            return dp[idx];
        }
        
        int minCost = Integer.MAX_VALUE;
        
        for(int jump = 1; jump <= k; jump++){
            if(idx + jump <= arr.length - 1){
                minCost = Math.min(
                    minCost, 
                    Math.abs(arr[idx] - arr[idx + jump]) + minimizeCostUtil(arr, idx + jump, k, dp)
                );
            }
        }
        return dp[idx] = minCost;
    }
    public int minimizeCost(int arr[], int n, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, -1);
        return minimizeCostUtil(arr, 0, k, dp);
    }
}
 

2. Tabulation:

class Solution {
    public int minimizeCost(int arr[], int n, int k) {
        int[] dp = new int[n];
        
        dp[arr.length - 1] = 0;
        
        for(int idx = arr.length - 2; idx >= 0; idx--){
            int minCost = Integer.MAX_VALUE;
            for(int jump = 1; jump <= k; jump++){
                if(idx + jump <= arr.length - 1){
                    int cost = Math.abs(arr[idx] - arr[idx + jump]) + dp[idx + jump];
                    minCost = Math.min(minCost, cost);
                }
            }
            dp[idx] = minCost;
        }
        
        return dp[0];
    }
}