// Frog Jump via Memoization

// tc = O(n)

// sc = O(n) + O(n) --> stack space + extra dp array

import java.util.*;

public class dp {

    public static int func(int index, int height[], int dp[]) {

        if(index==0) return 0;

        if(dp[index] != -1) return dp[index];

        int left_jmpOne = func(index-1,height,dp) + Math.abs(height[index] - height[index-1]);

        int right_jmpTwo = Integer.MAX_VALUE;

        if(index>1)

        {

            right_jmpTwo = func(index-2,height,dp) + Math.abs(height[index] - height[index-2]);

        }

        return dp[index] = Math.min(left_jmpOne,right_jmpTwo);

    }

    public static void main(String[] args) {

        int height[]={30,10,60,10,60,50};

        int n = 5; // n = height.length

        int dp[] = new int[n+1];

        Arrays.fill(dp,-1);

        System.out.println(func(n,height,dp)); // then n-1 here

    }

}