Dynamic Programming Lecture 3: Frog Jump

Introduction

• Welcome to Lecture 3 of the Dynamic Programming playlist.
• Ensure you've watched the first two lectures for context.
• Problem focus: Finding the minimum energy for a frog to jump to the nth stair.

Problem Statement

• Frog starts on the first step of a staircase with n stairs.
• Heights of stairs given by height array, 0-indexed.
• Frog can jump to i+1 or i+2 stairs.
• Energy for a jump from step i to j is abs(height[i] - height[j]).
• Task: Calculate the minimum energy required to reach the nth stair.

Example Explained

Example Array: [10, 20, 30, 10]

1. Converting the problem to 0-based indexing (0 to 3 for n=4).
2. Analyzing all paths and computing energies:
   • Path 1: Jumps: 0->1->2->3; Energy sum: 10 + 10 + 20 = 40.
   • Path 2: Jumps: 0->1->3; Energy sum: 10 + 10 = 20.
   • Path 3: Jumps: 0->2->3; Energy sum: 20 + 20 = 40.
3. Minimum energy is 20.

Problem Analysis

• Identifying all potential paths suggests using recursion.
• The problem is about finding the minimum energy path, not just any path, which rules out a greedy approach.
• Greedy may fail for cases where initial choices look optimal but later choices become suboptimal.

Greedy Failure Example:

• Array: [10, 20, 50, 10, 0, 40]
• Incorrect Greedy path leads to higher energy sum compared to trying all possibilities.

Recursion Approach

1. Express problem in terms of indexes.
2. Do all operations on that index: Jumps of +1 and +2.
3. Take the minimum of all possible sums:
   • Define f(n-1) as minimum energy from 0 to n-1.
   • Recurrence relation: f(idx) = min(f(idx-1) + |a[idx] - a[idx-1]|, f(idx-2) + |a[idx] - a[idx-2]|).
   • Base case: f(0) = 0 (energy to stay at the start).

Overlapping Subproblems and Memoization

• Recursive calls show overlapping subproblems (e.g., multiple calls to f(3)).
• Memoization stores subproblem solutions to avoid repeated calculation.
• DP array size n+1 (index up to n-1), initialize DP array with -1.
• Pass DP reference in recursive calls and update it.

Recursive Code in a Nutshell

Initialization of DP, base case handling, recursion with checks.

int func(int index, vector<int>& heights, vector<int>& dp) {
  if (index == 0) return 0;
  if (dp[index] != -1) return dp[index];
  int left = func(index - 1, heights, dp) + abs(heights[index] - heights[index - 1]);
  int right = INT_MAX;
  if (index > 1) right = func(index - 2, heights, dp) + abs(heights[index] - heights[index - 2]);
  return dp[index] = min(left, right);
}

Iterative DP (Tabulation)

• Convert recursion to DP by filling a table bottom up.
• Initialize DP array.
• Iteratively compute values up to n-1.

Tabulation Code

vector<int> dp(n, INT_MAX);
dp[0] = 0;
for (int i = 1; i < n; ++i) {
  int stepOne = dp[i - 1] + abs(heights[i] - heights[i - 1]);
  int stepTwo = (i > 1) ? dp[i - 2] + abs(heights[i] - heights[i - 2]) : INT_MAX;
  dp[i] = min(stepOne, stepTwo);
}
return dp[n - 1];

Space Optimization

• Space optimization possible as we only use values of i-1 and i-2, can be stored in two variables.

Optimized Code

int prev2 = 0, prev1 = 0;
for (int i = 1; i < n; ++i) {
  int curr = min(prev1 + abs(heights[i] - heights[i - 1]),
                 (i > 1) ? prev2 + abs(heights[i] - heights[i - 2]) : INT_MAX);
  prev2 = prev1;
  prev1 = curr;
}
return prev1;

Homework Exercise

• Adapt solution for up to k jumps (instead of just i+1 and i+2).
• Consider optimization limitations discussed.

Conclusion

• Like, comment 'understood', and subscribe to the channel.
• Share the video and check out the SD sheet available in the channel description.
• Stay tuned for the next lecture!