Frog Jump
1D DP DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Minimum energy frog jump problem on stairs, Dynamic Programming, Recursion, Memoization, Tabulation, Space Optimization, Time Complexity, Space Complexity, Arrays, Greedy Algorithm, Absolute Difference, dynamic programming, memoization, mathematical operations, tabulation, shortest path algorithms, space optimization, recursion, Grid / Matrix DP.
Frog Jump Problem Statement Given a number of stairs, N, and an array height of size N, where height[i] represents the height of the i th stair. A frog wants to climb from the 0th stair to the (N 1)th stair. At a time, the frog can climb either one or two steps. When the frog jumps from stair i to stair j, the energy consumed in the jump is abs(height[i] height[j]), where abs() denotes the absolute difference. Your task is to find and return the minimum energy that can be used by the frog to jump from stair 0 to stair N 1. Input Specification An integer N representing the total number of stairs. An array height of N integers, where height[i] is the height of the i th stair. Output Specification Return an integer representing the minimum energy consumed by the frog to reach the (N 1)th stair. Sample Test Case Input: N = 6 height = [30, 10, 60, 10, 60, 50] Output: 40 Explanation: The optimal path for the frog to minimize energy consumption is as follows: Jump from stair 0 (height 30) to stair 1 (height 10): Energy = abs(30 10) = 20 Jump from stair 1 (height 10) to stair 3 (height 10): Energy = abs(10 10) = 0 Jump from stair 3 (height 10) to stair 5 (height 50): Energy = abs(10 50) = 40 Total minimum energy = 20 + 0 + 40 = 40.