🐸 Frog Jump – Dynamic Programming Implementation

This project implements the classic Frog Jump problem using Dynamic Programming techniques. The objective is to compute the minimum energy required for a frog to reach the last stone, given that it can jump either 1 or 2 steps at a time.

📌 Problem Statement Given an array heights[], where heights[i] represents the height of the i-th stone, a frog starts at index 0 and wants to reach index n-1. The frog can: Jump from i → i+1 Jump from i → i+2 The energy cost of a jump from stone i to j is: abs(heights[i] - heights[j])

Goal: Minimize the total energy cost required to reach the last stone.

🧠 Approach The problem is solved using Dynamic Programming with three approaches: Recursion + Memoization (Top-Down DP) Tabulation (Bottom-Up DP) Space Optimized DP (O(1) space) Recurrence Relation dp[i] = min( dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]) )

🚀 Time & Space Complexity Approach Time Complexity Space Complexity Memoization O(n) O(n) Tabulation O(n) O(n) Space Optimized O(n) O(1)

📂 Project Structure frog-jump/ │ ├── memoization.cpp ├── tabulation.cpp ├── space_optimized.cpp └── README.md

💡 Key Concepts Practiced State Definition Recurrence Design Dependency Direction Topological Order in DP Space Optimization

📈 Why This Project? This project demonstrates a fundamental 1D Dynamic Programming pattern and builds intuition for: House Robber Climbing Stairs Min Cost Climbing Stairs

K-step DP variations