Frog Jump with K Distances
1D DP DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Dynamic Programming: Frog Jump with K Distances (DP 4), Dynamic Programming, Memoization, Tabulation, Time Complexity, Space Complexity, Recursion, Arrays, Absolute Difference, complexity analysis, dynamic programming, memoization, array processing, optimization, tabulation, recursion, Matrix Manipulation.
Frog Jump with K Distances There are N stones, and the i th stone has a height of height[i]. A frog is currently on stone 0 and wants to reach stone N 1. From any stone i, the frog can jump to any stone j such that i < j <= i + k. The energy cost of jumping from stone i to stone j is |height[i] height[j]|. The frog wants to minimize the total energy cost to reach stone N 1. Input Specification The first line contains two integers, N and K, separated by a space, representing the number of stones and the maximum jump distance, respectively. The second line contains N integers, height[0], height[1], ..., height[N 1], separated by spaces, representing the heights of the stones. Output Specification Print a single integer, the minimum total energy cost to reach stone N 1. Constraints 1 <= N <= 10^5 1 <= K <= N 0 <= height[i] <= 10^4 Sample Test Cases Sample Input 1 Sample Output 1 Difficulty Level Medium