23456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354

class Solution {
    // Solve function using recursion with memoization
    // ind -> current index the frog needs to reach
    // height -> array of heights
    // dp -> memo table where dp[i] stores min cost to reach i
    solve(ind, height, dp) {
        // If at the first stone, cost is 0
        if (ind === 0) return 0;

        // Return memoized result if already computed
        if (dp[ind] !== -1) return dp[ind];

        // Initialize jumpTwo with a large value
        let jumpTwo = Number.POSITIVE_INFINITY;

        // Compute cost when jumping from previous stone (ind - 1)
        const jumpOne = this.solve(ind - 1, height, dp) + Math.abs(height[ind] - height[ind - 1]);

        // Compute cost when jumping from two stones back (ind - 2) if possible
        if (ind > 1) {
            jumpTwo = this.solve(ind - 2, height, dp) + Math.abs(height[ind] - height[ind - 2]);
        }

        // Memoize and return the minimum of the two choices
        dp[ind] = Math.min(jumpOne, jumpTwo);
        return dp[ind];
    }

    // Helper to handle edge cases and start recursion
    frogJump(height) {
        // Handle empty input
        if (!height || height.length === 0) return 0;

        // Prepare dp with -1 indicating uncomputed states
        const n = height.length;
        const dp = Array(n).fill(-1);

        // Start from the last index
        return this.solve(n - 1, height, dp);
    }
}

// Driver code
(function main() {
    // Define the heights array
    const height = [30, 10, 60, 10, 60, 50];

    // Create Solution instance
    const sol = new Solution();

    // Compute and print the minimum energy
    console.log(sol.frogJump(height)); // Expected: 40
})();

Complexity Analysis

Time Complexity: O(n), since each state (index) is computed once and stored in the DP array.

Space Complexity: O(n) for the DP array + O(n) recursion stack, leading to O(n) overall.

Tabulation Approach

Algorithm