Minimal Cost

There is an array arr of heights of stone and Geek is standing at the first stone and can jump to one of the following: Stone i+1, i+2, … i+k stone, where k is the maximum number of steps that can be jumped and cost will be |h_i-h_j| is incurred, where j is the stone to land on. Find the minimum possible total cost incurred before the Geek reaches the last stone.

Example:

Input: k = 3, arr[]= [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

Input: k = 1, arr[]= [10, 20, 10]
Output: 20
Explanation: Geek will follow the path 1->2->3, the total cost would be |10 - 20| + |20 - 10| = 20.

Expected Time Complexity: O(n*k)
Expected Auxilary Space: O(n)

Constraint:
1<= arr.size() <=10⁴
1 <= k <= 100
1 <= arr[i] <= 10⁴

Approach 01:

#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

class Solution {
public:
    // Function to recursively calculate the minimum cost to reach the last stone
    int calculateMinCost(int maxJump, vector<int>& heights, int totalStones, vector<int>& memo, int currentIndex) {
        // Base case: when we reach the last stone, no cost is needed
        if (currentIndex == totalStones - 1)
            return 0;
        
        // If already calculated, return the stored result
        if (memo[currentIndex] != -1)
            return memo[currentIndex];
        
        int minCost = INT_MAX;
        // Explore all possible jumps within the range of maxJump
        for (int nextIndex = currentIndex + 1; nextIndex <= min(currentIndex + maxJump, totalStones - 1); nextIndex++) {
            minCost = min(minCost, abs(heights[currentIndex] - heights[nextIndex]) + calculateMinCost(maxJump, heights, totalStones, memo, nextIndex));
        }
        
        // Memoize the result for future use
        return memo[currentIndex] = minCost;
    }

    // Function to find the minimum cost to jump from the first stone to the last stone
    int minimizeCost(int maxJump, vector<int>& heights) {
        int totalStones = heights.size();
        vector<int> memo(totalStones, -1);
        
        return calculateMinCost(maxJump, heights, totalStones, memo, 0);
    }
};

class Solution:
    # Function to recursively calculate the minimum cost to reach the last stone
    def calculateMinCost(self, maxJump, heights, totalStones, memo, currentIndex):
        # Base case: when we reach the last stone, no cost is needed
        if currentIndex == totalStones - 1:
            return 0
        
        # If already calculated, return the stored result
        if memo[currentIndex] != -1:
            return memo[currentIndex]
        
        minCost = float('inf')
        # Explore all possible jumps within the range of maxJump
        for nextIndex in range(currentIndex + 1, min(currentIndex + maxJump + 1, totalStones)):
            minCost = min(minCost, abs(heights[currentIndex] - heights[nextIndex]) + 
                          self.calculateMinCost(maxJump, heights, totalStones, memo, nextIndex))
        
        # Memoize the result for future use
        memo[currentIndex] = minCost
        return minCost

    # Function to find the minimum cost to jump from the first stone to the last stone
    def minimizeCost(self, maxJump, heights):
        totalStones = len(heights)
        memo = [-1] * totalStones
        
        return self.calculateMinCost(maxJump, heights, totalStones, memo, 0)

Time Complexity

• Recursive Function Calls:

  The recursion explores each stone starting from the first stone. For each stone, it checks up to maxJump stones ahead, creating a branching factor. In the worst case, the function recursively calls itself up to maxJump times for each stone, resulting in a complexity of \(O(n \cdot \text{maxJump})\), where n is the number of stones.

• Memoization:

  Each stone’s result is computed only once due to memoization, preventing repeated work. This ensures that the total number of calculations remains \(O(n \cdot \text{maxJump})\).

• Overall Time Complexity:

  The overall time complexity is \(O(n \cdot \text{maxJump})\), where n is the number of stones and maxJump is the maximum jump length allowed.

Space Complexity

• Memoization Array:

  The memo array stores the minimum cost to reach the last stone from each stone. Its size is proportional to the number of stones, i.e., \(O(n)\).

• Recursive Stack Space:

  The recursion depth can go up to n (the number of stones), which results in a stack space complexity of \(O(n)\).

• Overall Space Complexity:

  The overall space complexity is \(O(n)\), where n is the number of stones due to the memoization array and recursive stack space.