# Frog Jump - Coding Ninjas

{% embed url="<https://www.codingninjas.com/codestudio/problems/frog-jump_3621012>" %}

This is also similar to Climbing stairs problem. The constraints are same except here there is a cost /energy associated with each jump. And the stairs index start from 1.&#x20;

We need to find out what is the minimum amount of enery required for reaching the last step or $$n^{th}$$step.

## Intuition

We cannot go with greedy method as it optimizes for local maxima and not global maxima

<figure><img src="https://1388126071-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVQ7Ie-PZpN_8yApX0-%2Fuploads%2FaGjULxqj9d0IDsYq085m%2Fimage.png?alt=media&#x26;token=e4280174-c9cb-43eb-bcdb-50643cb9df09" alt=""><figcaption></figcaption></figure>

#### Top Down

<figure><img src="https://1388126071-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVQ7Ie-PZpN_8yApX0-%2Fuploads%2FwEVcy9ACg356suvjCjTX%2Fimage.png?alt=media&#x26;token=adfb1427-bd0f-494a-9608-8aba5a28ca91" alt=""><figcaption></figcaption></figure>

#### Bottom Up

<figure><img src="https://1388126071-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVQ7Ie-PZpN_8yApX0-%2Fuploads%2FIk6Zxs8FQt97rBeMOnks%2Fimage.png?alt=media&#x26;token=70fbb771-3b05-411b-ac1f-0bc30ea2d4f2" alt=""><figcaption></figcaption></figure>

![](https://1388126071-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVQ7Ie-PZpN_8yApX0-%2Fuploads%2FC7BI3Zto9HpBTGSJRfVZ%2Fimage.png?alt=media\&token=77174c63-6c47-46fb-bb10-8bd3f56b1aae)![](https://1388126071-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVQ7Ie-PZpN_8yApX0-%2Fuploads%2FtAIEHeV5BvJ9m5m8ntnj%2Fimage.png?alt=media\&token=a5be9760-f613-4802-9167-ce7c78505d9a)

![](https://1388126071-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVQ7Ie-PZpN_8yApX0-%2Fuploads%2FQvd9whSvEHNn93QUAaaI%2Fimage.png?alt=media\&token=861214f9-614c-41e4-afce-ff791e9f7ff5)![](https://1388126071-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVQ7Ie-PZpN_8yApX0-%2Fuploads%2F4ihfXIS3kkcjeovEoHHp%2Fimage.png?alt=media\&token=d385c66a-d85a-46e4-a294-2475a83c4b57)

{% tabs %}
{% tab title="Top Down" %}

```java
import java.util.*;
import java.io.*;


public class Solution {

    public static int frogJump(int n, int heights[]) {
        // n -> number of stairs to climb
        // Time Complexity: O(n), to traverse through each step and check min
        // Space Complexity: O(n), to store min values
        
        // Create an array to store the minimum cost of frog jumps for each position
        // Initialise the size of dp array to "n"
        int[] dp = new int[n];

        // Initialize the dp array with -1 to indicate that the minimum cost is not yet computed
        Arrays.fill(dp, -1);

        // Call the helper function to calculate the minimum cost
        helper(n - 1, heights, dp);

        // Return the minimum cost for the last position as "n-1"
        // because it starts from 1st step
        return dp[n - 1];
    }

    // Helper function to calculate the minimum cost of frog jumps
    private static int helper(int n, int[] heights, int[] dp) {
        // Base case: reached the starting position (cost is 0)
        if (n == 0) {
            return 0;
        }

        // If the minimum cost for the current position is already computed, return the precalculated value
        if (dp[n] != -1) {
            return dp[n];
        }

        // Calculate the cost of jumping to the current position from the previous positions
        int left = helper(n - 1, heights, dp) + Math.abs(heights[n] - heights[n - 1]);

        // Initialize the cost of jumping from the position two steps ago as a large value
        int right = Integer.MAX_VALUE;

        // If there is a position two steps ago, calculate the cost of jumping from that position
        if (n > 1) {
            right = helper(n - 2, heights, dp) + Math.abs(heights[n] - heights[n - 2]);
        }

        // Store the minimum cost in the dp array for future use
        return dp[n] = Math.min(left, right);
    }
}
```

{% endtab %}

{% tab title="Bottom Up" %}

```java
import java.util.*;
import java.io.*;

public class Solution {
    public static int frogJump(int n, int heights[]) {
        // n -> number of stairs to climb
        // Time Complexity: O(n), to traverse through each step and check min
        // Space Complexity: O(n), to store min values
        
        // Create an array to store the minimum cost of frog jumps for each position
        int[] dp = new int[n];

        // Iterate through each position from left to right
        for (int i = 1; i < n; i++) {
            // Calculate the cost of jumping to the current position from the previous position (one step jump)
            int stepOneJump = dp[i - 1] + Math.abs(heights[i] - heights[i - 1]);

            // Initialize the cost of jumping from the position two steps ago as a large value
            int stepTwoJump = Integer.MAX_VALUE;

            // If there is a position two steps ago, calculate the cost of jumping from that position (two steps jump)
            if (i > 1) {
                stepTwoJump = dp[i - 2] + Math.abs(heights[i] - heights[i - 2]);
            }

            // Store the minimum cost of the two jump options in the dp array for the current position
            dp[i] = Math.min(stepOneJump, stepTwoJump);
        }

        // Return the minimum cost for the last position as "n-1"
        // because it starts at 1st step
        return dp[n - 1];
    }
}

```

{% endtab %}

{% tab title="BottomUp Space Optimisation" %}

{% endtab %}
{% endtabs %}
