Flashcards for:
Dynamic Programming Lecture 3: Frog Jump

A vector (array) named 'dp' of size n+1 is used to store the minimum energies computed for each step index by the recursive function to avoid redundant calculations.

The iterative approach initializes a DP array and fills it bottom-up. For each step i, it calculates the minimum energy by considering jumps from the previous step or the step before that, ensuring all subproblems are solved iteratively.

The second path (0->1->3) is chosen as the optimal solution because the sum of the energies, 10 (jump from 0 to 1) + 10 (jump from 1 to 3), equals 20, which is the minimum compared to other paths.

The problem is modeled using a function f(idx) which represents the minimum energy required to reach step idx. The function relies on recursive calls to f(idx-1) and f(idx-2) with the addition of the energy for each corresponding jump.

To adapt the solution for jumps up to 'k' steps, modify the DP recurrence relation to: f(idx) = min(f(idx-j) + abs(height[idx] - height[idx-j])) for all 1 ≤ j ≤ k, and iterate through all possible jumps from the current step.

Memoization helps by storing the results of subproblems in a DP array to avoid redundant calculations, ensuring that each subproblem is solved only once and accessed in constant time when needed.

The recurrence relation is: f(idx) = min(f(idx-1) + abs(height[idx] - height[idx-1]), f(idx-2) + abs(height[idx] - height[idx-2]))

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];

A greedy approach is not suitable because it might miss the optimal path by making locally optimal choices that lead to suboptimal total energy. Instead, the problem requires evaluating all possible paths which is better handled by dynamic programming.

Space can be optimized by using only two variables (prev1 and prev2) to store the last two states needed to compute the current state's energy, reducing the space complexity from O(n) to O(1).

The base case for the recursion is when the frog is already at the starting step (index 0), where the energy required is zero, i.e., f(0) = 0.

The time complexity of the space-optimized iterative approach is O(n) because it involves a single loop through the n steps, computing the minimum energy required for each step.

For large values of 'n', the DP approach that uses an O(n) space complexity might be memory intensive. The space-optimized version helps mitigate this by reducing the space complexity to O(1).

An initialization of the DP array with size n+1, filled with a default value (e.g., -1) to indicate uncalculated states, is required. Additionally, base case(s) must be set appropriately, such as dp[0] = 0.

A frog starts at the first step of an n-step staircase and can jump to either i+1 or i+2 steps. The energy required for each jump is given by the absolute difference in heights of the stairs. The task is to find the minimum energy needed for the frog to reach the nth stair.