Frog Jump

// Frog Jump - In Minimum Energy To Reach End

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

-----------------------------------------------------------------------------------------------------------------------------------------------
//  Recursion + Memoization Approach ( Top-Down ) 
TC - O(N)
SC - O(N) + O(N)
public class Solution {
    private static int[] dp;
    public static int frogJump(int n, int arr[]) {

        // Write your code here
        dp = new int[n+1];
        Arrays.fill(dp, -1);
        return helper(0, n, arr);
    }

    private static int helper
    (
        int i, 
        int n, 
        int[] arr
    ) {
        if (i >= n) {
            return Integer.MAX_VALUE;
        }
        if (i == n-1) {
            return 0;
        }

        if (dp[i] != -1) {
            return dp[i];
        }
        int firstJump = helper(i+1, n, arr) + Math.abs(arr[i] - arr[i+1]);
        int secondJump = Integer.MAX_VALUE;
        if (i+2 <= n-1) {
            secondJump = helper(i+2, n, arr) + Math.abs(arr[i] - arr[i+2]);
        }

        return dp[i] = Math.min(firstJump, secondJump);
    }
}


-----------------------------------------------------------------------------------------------------------------------------------------------
// Tabulation Approach ( Bottom-Up )
TC - O(N)
SC - O(N)
public class Solution {
    public static int frogJump(int n, int arr[]) {

        // Write your code here
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i=1; i<n; i++) {
            int first = dp[i-1] + Math.abs(arr[i]-arr[i-1]);
            int second = Integer.MAX_VALUE;
            if (i > 1) {
                second = dp[i-2] + Math.abs(arr[i]-arr[i-2]);
            }

            dp[i] = Math.min(first, second);
        }

        return dp[n-1];
    }

}


-----------------------------------------------------------------------------------------------------------------------------------------------
// Space Optimization
TC - O(N)
SC - O(1)
public class Solution {
    public static int frogJump(int n, int arr[]) {

        // Write your code here
        int dp1 = 0;
        int dp2 = 0;

        for (int i=1; i<n; i++) {
            int first = dp2 + Math.abs(arr[i]-arr[i-1]);    // Instade using DP array be use couple of arrays to reduce the space
            int second = Integer.MAX_VALUE;
            if (i > 1) {
                second = dp1 + Math.abs(arr[i]-arr[i-2]);
            }

            int third = Math.min(first, second);
            dp1 = dp2;
            dp2 = third;
        }

        return dp2;
    }
}