DP 3. Frog Jump | Dynamic Programming

Welcome to the third lecture of the Dynamic Programming series. This chapter explores the classic "Frog Jump" problem, transitioning from a naive recursive approach to optimized memoization, tabulation, and ultimately, space-optimized dynamic programming.

1. Problem Statement & The Core Challenge

Imagine a frog sitting on the $0^{\text{th}}$ stair of an $N$-stair staircase (using 0-based indexing). The frog wants to reach the $(N-1)^{\text{th}}$ stair.

• Allowed Moves: From the $i^{\text{th}}$ stair, the frog can jump either to stair $i + 1$ or stair $i + 2$.
• Energy Cost: The energy lost in jumping from stair $i$ to stair $j$ is the absolute difference of their heights: $\vert \text{height}[i] - \text{height}[j]\vert$.
• Objective: Find the minimum total energy required for the frog to travel from the 0th stair to the $(N-1)^{\text{th}}$ stair.

Real-Life Analogy: Navigating Obstacles

Analogy: Think of the frog as a hiker trying to descend or ascend a series of ledges of varying heights. Taking a giant leap ($i + 2$) might bypass a steep drop or spike in energy expenditure, whereas taking single steps ($i + 1$) accumulates smaller increments. Because choices compound over the journey, you cannot simply look at the immediate next step; you must evaluate how future choices align to minimize the total cumulative effort.

2. Why a Greedy Approach Fails

It is natural to wonder: Why not just pick the locally optimal (minimum energy) jump at every step?

Let's examine a counterexample where a greedy strategy breaks down:

Heights array: [30, 10, 60, 10, 60, 50]

• Greedy Choice: Standing at index 0 (height 30), the frog sees indices 1 (10) and 2 (60).
  • The greedy choice is to jump to index 1, costing $\vert 30 - 10\vert = 20$.
  • From index 1 (10), the frog can jump to index 2 (60) costing $50$, or index 3 (10) costing $0$.
  • Greedily picking index 3 (10) costs $0$.
  • Continuing this greedy path forces future suboptimal leaps, leading to a total cost of 60.
• Optimal Choice: By taking a larger initial jump or alternating paths strategically (e.g., jumping from index 0 to 2, then 4, then 5), the total energy can be reduced to 40.

Conclusion: When local choices blind you to future savings or penalties, greedy algorithms fail. Whenever a problem asks you to try all possible paths and find the best (minimum/maximum) outcome, Recursion / Dynamic Programming is required.

3. Expressing the Problem as a Recursive Definition

To solve any DP problem using recursion, follow these three foundational steps:

1. Express the problem in terms of an index.
2. Do all possible choices/stuffs on that index.
3. Take the minimum (or maximum) of all choices.

Defining the Function

Let f(index) represent the minimum energy required to reach the given index starting from index 0.

• Base Case: To reach index 0 from index 0, the energy required is 0. Thus, f(0) = 0.
• Recursive Transitions: From any index, the frog has two choices:
  • Left Jump (1 step back): Jump from index - 1 to index. Cost = |heights[index] - heights[index - 1]| + f(index - 1).
  • Right Jump (2 steps back): Jump from index - 2 to index. Cost = |heights[index] - heights[index - 2]| + f(index - 2). (Valid only if index > 1)

4. Naive Recursive Solution

Below is the unoptimized recursive implementation in C++ reflecting the logic above:

#include <bits/stdc++.h>
using namespace std;

int solve(int ind, vector<int>& heights) {
    // Base Case
    if (ind == 0) return 0;
    
    // Left recursive call (1 step jump)
    int left = solve(ind - 1, heights) + abs(heights[ind] - heights[ind - 1]);
    
    // Right recursive call (2 step jump - valid only if ind > 1)
    int right = INT_MAX;
    if (ind > 1) {
        right = solve(ind - 2, heights) + abs(heights[ind] - heights[ind - 2]);
    }
    
    return min(left, right);
}

int frogJump(int n, vector<int>& heights) {
    return solve(n - 1, heights);
}

Performance Note: This naive recursion suffers from overlapping subproblems (recomputing the same index multiple times), leading to an exponential time complexity of $O(2^N)$ and hitting Time Limit Exceeded (TLE) on larger test cases.

5. Top-Down Approach: Memoization

To eliminate redundant calculations, we store the result of each subproblem in a dp array initialized to -1.

Memoization Steps:

1. Declare a dp array of size N + 1 initialized with -1.
2. Check memoized state: Before solving a subproblem ind, check if dp[ind] != -1. If so, return it directly.
3. Store before return: Store the computed minimum in dp[ind] right before returning.

C++ Memoized Implementation

#include <bits/stdc++.h>
using namespace std;

int solveMem(int ind, vector<int>& heights, vector<int>& dp) {
    if (ind == 0) return 0;
    
    // Step 3: Return if already computed
    if (dp[ind] != -1) return dp[ind];
    
    int left = solveMem(ind - 1, heights, dp) + abs(heights[ind] - heights[ind - 1]);
    
    int right = INT_MAX;
    if (ind > 1) {
        right = solveMem(ind - 2, heights, dp) + abs(heights[ind] - heights[ind - 2]);
    }
    
    // Step 2: Store in dp array before returning
    return dp[ind] = min(left, right);
}

int frogJump(int n, vector<int>& heights) {
    // Step 1: Initialize dp array of size n with -1
    vector<int> dp(n, -1);
    return solveMem(n - 1, heights, dp);
}

• Time Complexity: $O(N)$ — each state from 0 to N-1 is computed only once.
• Space Complexity: $O(N)$ for the recursion stack space + $O(N)$ for the dp table.

6. Bottom-Up Approach: Tabulation

Tabulation converts the top-down memoized solution into an iterative bottom-up approach. Instead of starting from N-1 and going down to 0, we start building solutions from 0 up to N-1.

Tabulation Transformation Rules:

1. Initialize the dp array of size N with 0.
2. Set the base case: dp[0] = 0.
3. Run a loop from i = 1 to N - 1.
4. Compute left and right using previously computed table values (dp[i-1] and dp[i-2]).

C++ Tabulated Implementation

#include <bits/stdc++.h>
using namespace std;

int frogJumpTabulation(int n, vector<int>& heights) {
    vector<int> dp(n, 0);
    dp[0] = 0;
    
    for (int i = 1; i < n; i++) {
        int fs = dp[i - 1] + abs(heights[i] - heights[i - 1]);
        int ss = INT_MAX;
        if (i > 1) {
            ss = dp[i - 2] + abs(heights[i] - heights[i - 2]);
        }
        dp[i] = min(fs, ss);
    }
    
    return dp[n - 1];
}

• Time Complexity: $O(N)$
• Space Complexity: $O(N)$ (storing the dp array).

7. Space Optimization

Notice how to compute the answer for any index i, we only ever look back at the previous two states (i-1 and i-2). We do not need a full array of size N. We can compress our memory footprint down to constant space $O(1)$ by tracking just a few variables.

C++ Space-Optimized Implementation

#include <bits/stdc++.h>
using namespace std;

int frogJumpSpaceOptimized(int n, vector<int>& heights) {
    int prev = 0;      // represents dp[i-1]
    int prev2 = 0;     // represents dp[i-2]
    
    for (int i = 1; i < n; i++) {
        int fs = prev + abs(heights[i] - heights[i - 1]);
        int ss = INT_MAX;
        if (i > 1) {
            ss = prev2 + abs(heights[i] - heights[i - 2]);
        }
        
        int curr = min(fs, ss);
        
        // Shift pointers forward for the next iteration
        prev2 = prev;
        prev = curr;
    }
    
    return prev; // At the end, 'prev' holds the answer for n-1
}

• Time Complexity: $O(N)$
• Space Complexity: $O(1)$ — optimal memory utilization!

8. Summary Comparison Table

9. Summary and Key Takeaways

• Greedy algorithms fail when local optimal choices prevent achieving the global optimum; full exploration via recursion is necessary.
• Three-Step Recursion Framework: (1) Express problem in terms of index, (2) Explore all choices on that index, (3) Take the minimum/maximum of choices.
• Overlapping Subproblems indicate that Dynamic Programming can be applied to transform exponential solutions into linear time solutions.
• Top-Down (Memoization) adds a lookup table to recursion, preventing redundant work.
• Bottom-Up (Tabulation) replaces recursive stack overhead with an iterative loop.
• Space Optimization is always possible when transitions depend only on a fixed, constant number of preceding states ($O(1)$ space).
• Homework Challenge: Try solving the $K$-Jumps variant where the frog can jump up to $K$ stairs ahead instead of just 2!