🗓️ Day 22: Frog Jump with Minimum Energy

📘 What You’ll Learn

How to solve the "Frog Jump" problem using DP
Comparing recursion, memoization, and tabulation
How to minimize energy cost across platforms
Transition logic in DP
An intro to space optimization in DP

🧠 Concept

A frog is jumping across stones. Each stone has a height, and the frog pays energy when it jumps. It can jump either 1 or 2 stones forward. The cost of each jump is the absolute height difference between the starting and landing stone.

Your goal? Minimize the total energy cost to reach the last stone.

Let:

dp[i] = min energy required to reach stone i

Transition:

dp[i] = min(
  dp[i - 1] + abs(heights[i] - heights[i - 1]),
  dp[i - 2] + abs(heights[i] - heights[i - 2])
);

With:

dp[0] = 0

📊 Visualization

Let heights = [30, 10, 60, 10, 60, 50]

Start at 0
=> Choose between:
  - jump to i-1 with cost |h[i] - h[i-1]|
  - jump to i-2 with cost |h[i] - h[i-2]|

Goal: get to last stone (index 5) with minimum total energy

💻 TypeScript Example

function frogJump(heights: number[]): number {
  const n = heights.length;
  let prev = 0;
  let prev2 = 0;

  for (let i = 1; i < n; i++) {
    const jumpOne = prev + Math.abs(heights[i] - heights[i - 1]);
    const jumpTwo = i > 1 ? prev2 + Math.abs(heights[i] - heights[i - 2]) : Infinity;
    const curr = Math.min(jumpOne, jumpTwo);
    prev2 = prev;
    prev = curr;
  }

  return prev;
}

⏱️ Time: O(n)
💾 Space: O(1) (optimized from O(n))

🧪 LeetCode Homework

📘 GeekforGeeks: Frog Jump with K Distance

Each jump can be up to k steps. Try generalizing the logic.

📘 746. Min Cost Climbing Stairs

Very similar idea, except you pay a cost at each step.

console.log(frogJump([30,10,60,10,60,50])); // 40

📌 Key Takeaways

Great pattern to master space optimization
Learn to translate problem constraints into DP transitions
Base cases matter!
Cost functions in DP show up everywhere: energy, coins, time, etc.

🔮 Up Next

▶️ Day 23: 0/1 Knapsack Intro