Dynamic Programming Lecture 3: Frog Jump

Introduction

• Topic: Frog Jump problem in dynamic programming.
• Prerequisite: Previous lectures in the dynamic programming playlist should be watched for better understanding.

Problem Statement

• A frog is on the first step of a staircase with n stairs.
• The frog's goal is to reach the nth stair.
• The height of the stairs is given in an array using zero-based indexing.
• Energy lost in a jump from stair i to stair j is given by:
  energy = height[i] - height[j]
• The frog can jump to either the (i+1)th stair or the (i+2)th stair.
• Task: Calculate the minimum total energy used by the frog to reach the nth stair.

Example

• Given heights: [10, 20, 30, 10]
• Zero-based indexing: 0, 1, 2, 3
• Possible paths and energy costs:
  • Path 1: 0 -> 1 -> 2 -> 3 (cost = 10 + 10 + 20 = 40)
  • Path 2: 0 -> 2 -> 3 (cost = 20)
• Minimum energy found = 20.

Recursion Approach

• Trying all possible paths implies using recursion.
• Why Greedy Approach Fails:
  • Greedily opting for the minimal energy jump might lead to suboptimal paths.
  • Example: Jumping to the nearest stair may not yield the best overall energy cost.

Steps to Write Recursion

1. Express Problem in Terms of Index: Use array indices to represent the stairs.
2. Define Function: Let f(n) be the minimum energy required to reach the nth stair.
3. Base Case:
   • f(0) = 0 (cost to stay on the first stair is zero).
4. Recurrence Relation:
   • For each stair, derive the cost from possible jumps:
     • f(i) = min(f(i-1) + abs(height[i] - height[i-1]), f(i-2) + abs(height[i] - height[i-2]))
   • Only calculate f(i-2) if i > 1.

Memoization

• Overlapping Subproblems:
  • Once a stair's minimum energy is calculated, store it to avoid redundant calculations.
• How to Apply Memoization:
  1. Declare a DP array of size n+1.
  2. Before returning a value in the recursive function, check if it's already computed.
  3. Store the computed result:
     • dp[i] = min(dp[i], computed_result).

Time Complexity

• The time complexity is O(n) due to linear recursion calls and storing results.

Tabulation Approach

• Bottom-Up Approach: Fill the DP array from bottom to top.
• Implement similar logic as in recursion, looping through all stairs.
• Base case: dp[0] = 0.

Space Optimization

• Instead of a DP array, use two variables to keep track of the previous two results needed for calculation.
• Final implementation:
  • Use variables prev1 and prev2 to calculate the minimum energy iteratively.

Follow-up Problem

• K Jumps:
  • Modify the problem such that the frog can jump up to k stairs (i.e., i + 1 to i + k).
  • Note: Space optimization may not apply as multiple previous results need to be maintained.

Conclusion

• Recursion, memoization, tabulation, and space optimization are key concepts for solving dynamic programming problems like Frog Jump.
• Encourage sharing insights and discussing follow-up problems in the comments.