Minimal Cost

JavaView on GFG

Intuition

Minimum cost to make at most k jumps from first to last stone. Greedy or DP.

Algorithm

1Sort heights. With k jumps allowed: skip the k-1 largest gaps between consecutive stones.

Common Pitfalls

•Key insight: if you can make k jumps, you skip k-1 intermediate stones choosing the largest height differences.

Minimal Cost.java

Java

// Approach: Greedy. Sort the differences between consecutive stones. Skip k-1 largest gaps (jump over them).
// Time: O(n log n) Space: O(n)
class Solution {
    public int minimizeCost(int k, int arr[]) {
        int n = arr.length;
        int[] dp = new int[n];

        Arrays.fill(dp, -1);

        return getMinCost(arr, k, 0, dp);
    }

    public int getMinCost(int[] arr, int k, int index, int[] dp) {
        if (index == arr.length - 1)
            return 0;

        if (dp[index] != -1)
            return dp[index];

        int mini = Integer.MAX_VALUE;

        for (int i = 1; i <= k && (index + i < arr.length); i++) {
            int cost = Math.abs(arr[index + i] - arr[index]) + getMinCost(arr, k, index + i, dp);

            mini = Math.min(mini, cost);
        }
        dp[index] = mini;

        return mini;
    }
}

Was this solution helpful?