DP 4. Frog Jump with K Distance (Lecture 3 Follow-Up Question)

1. Problem Statement & Extension from Lecture 3

In Lecture 3, we solved the classic Frog Jump problem where a frog starting at index 0 could only jump to adjacent steps: i + 1 or i + 2, incurring an energy cost equal to the absolute difference in heights (|heights[i] - heights[dest]|). The objective was to reach the final index n - 1 with the minimum total energy.

This chapter examines the natural follow-up extension: What if the frog is allowed to jump up to $K$ distances ahead? Instead of being restricted to just 1 or 2 steps, the frog can now jump from index i to any index in the range:

2. Core Mental Model: Generalizing the Transitions

In Lecture 3, the recurrence relationship evaluated exactly two choices (step 1 and step 2) and took their minimum:

• Jump 1: Reach index - 1 and add |heights[index] - heights[index - 1]|
• Jump 2: Reach index - 2 and add |heights[index] - heights[index - 2]|
• Recurrence: f(index) = min(Jump 1, Jump 2)

Scaling to $K$ Possible Jumps

When the jump capacity expands to $K$ steps, the frog evaluates $K$ distinct choices for every single index:

• Jump 1: index - 1
• Jump 2: index - 2
• Jump 3: index - 3
• ...
• Jump K: index - K

Rather than manually writing out redundant lines for a 3rd step, 4th step, etc., we replace the hardcoded choices with a dynamic loop that iterates through all possible jump sizes from j = 1 to k.

3. Recursive Solution with Memoization

We define our base case and recursive function f(index):

• Base Case: If index == 0, the frog is already at the starting position; return 0 energy.
• Transition: Initialize minSteps = INT_MAX, then iterate j from 1 to K. For each valid jump where index - j >= 0, calculate the energy cost and update minSteps.

Recursive Code Structure

int solveUtil(int index, vector<int>& height, vector<int>& dp, int k) {
    if (index == 0) return 0;
    
    if (dp[index] != -1) return dp[index];
    
    int minSteps = INT_MAX;
    
    for (int j = 1; j <= k; j++) {
        if (index - j >= 0) {
            int jumpEnergy = solveUtil(index - j, height, dp, k) + abs(height[index] - height[index - j]);
            minSteps = min(minSteps, jumpEnergy);
        }
    }
    
    return dp[index] = minSteps;
}

4. Tabulation (Bottom-Up Dynamic Programming)

To eliminate recursion stack overhead, we convert the top-down memoized approach into a bottom-up iterative table (dp array).

Tabulation Workflow

1. Declare a dp array of size n initialized to 0 or appropriate default values.
2. Set the base case: dp[0] = 0 (energy to reach index 0 from 0 is 0).
3. Run an outer loop from i = 1 to n - 1 to fill the table state by state.
4. Inside the outer loop, run an inner loop for each jump size j from 1 to K.

Tabulation Code Implementation

int frogJumpK(int n, int k, vector<int>& height) {
    vector<int> dp(n, 0);
    dp[0] = 0;
    
    for (int i = 1; i < n; i++) {
        int minSteps = INT_MAX;
        
        for (int j = 1; j <= k; j++) {
            if (i - j >= 0) {
                int jumpEnergy = dp[i - j] + abs(height[i] - height[i - j]);
                minSteps = min(minSteps, jumpEnergy);
            }
        }
        dp[i] = minSteps;
    }
    
    return dp[n - 1];
}

5. Complexity Analysis

6. Can We Space-Optimize Further?

In standard Frog Jump ($K = 2$), we successfully optimized space complexity from $O(N)$ down to $O(1)$ by maintaining only the last 2 previous states (prev and prev2) instead of keeping an entire DP array.

Analyzing Space Optimization for $K$ Distance

• When $K = 2$, we needed the last 2 states: i - 1 and i - 2.
• When $K = 3$, we would need the last 3 states: i - 1, i - 2, and i - 3.
• In general, for a given $K$, computing state i requires the previous $K$ states (i - 1 down to i - K).

Why Full Space Optimization is Impractical

• While one could theoretically maintain a sliding window or list of size $K$ (dropping the oldest state and appending the current state), the worst-case scenario occurs when $K = N$.
• If $K$ can be as large as $N$, maintaining the last $K$ elements requires $O(N)$ space anyway.
• Therefore, space optimization yields no asymptotic improvement in the worst case ($O(K)$ space where $K$ approaches $N$), making the standard $O(N)$ DP array table approach the most practical and clean solution.

7. Summary and Key Takeaways

• Problem Extension: Generalizes the 2-step frog jump to allow variable jumps of length 1 up to $K$.
• Transition Rule: Instead of checking fixed choices, compute the minimum across a loop of $K$ prior states: dp[i - j] + abs(height[i] - height[i - j]).
• Boundary Validation: Always ensure that i - j >= 0 to prevent out-of-bounds indexing when evaluating jumps near the start.
• Time Complexity: Increased from $O(N)$ to $O(N \times K)$ due to the inner loop evaluating $K$ jumps per state.
• Space Complexity: Remains $O(N)$ for the tabulation table, as space optimization to $O(K)$ provides no benefit when $K$ approaches $N$ in the worst case.