Geek wants to climb from the 0th stair to the (n-1)th stair. At a time the Geek can climb either one or two steps. A height[N] array is also given. Whenever the geek jumps from stair i to stair j, the energy consumed in the jump is abs(height[i]- height[j]), where abs() means the absolute difference. return the minimum energy that can be used by the Geek to jump from stair 0 to stair N-1.
Example:
Input:
n = 4
height = {10 20 30 10}
Output:
20
Explanation:
Geek jump from 1st to 2nd stair(|20-10| = 10 energy lost).
Then a jump from the 2nd to the last stair(|10-20| = 10 energy lost).
so, total energy lost is 20 which is the minimum.
Your Task:
You don't need to read input or print anything. Your task is to complete the function MinimumEnergy() which takes the array height, and integer n, and returns the minimum energy that is lost.
Expected Time Complexity: O(n)
Expected Space Complexity: O(n)
Constraint:
1<=n<=100000
1<=height[i]<=1000

Source: geeksforgeeks | Difficulty: EASY

Starter code: #User function Template for python3



class Solution:

    def minimumEnergy(self, height, n):

        # Code here

Solutions:
import sys

class Solution:

	def minimumEnergy(self, height, n):
		prev = 0
		prev2 = 0
		for i in range(1, n, 1):
			first = prev + abs(height[i] - height[i - 1])
			second = sys.maxsize
			if i > 1:
				second = prev2 + abs(height[i] - height[i - 2])
			curr = min(first, second)
			prev2 = prev
			prev = curr
		return prev


class Solution:

	def findMinEnergy(self, height, index, dp):
		if index == 0:
			return 0
		if dp[index] != -1:
			return dp[index]
		left = Solution.findMinEnergy(self, height, index - 1, dp) + abs(height[index] - height[index - 1])
		right = 1000000000.0
		if index > 1:
			right = Solution.findMinEnergy(self, height, index - 2, dp) + abs(height[index] - height[index - 2])
		dp[index] = min(left, right)
		return dp[index]

	def minimumEnergy(self, height, n):
		dp = [0] * n
		prev = 0
		prev2 = 0
		for index in range(1, n):
			fs = prev + abs(height[index] - height[index - 1])
			ss = 1000000000.0
			if index > 1:
				ss = prev2 + abs(height[index] - height[index - 2])
			curr = min(fs, ss)
			prev2 = prev
			prev = curr
		return prev


class Solution:

	def minimumEnergy(self, height, n):
		prev1 = 0
		prev2 = 0
		for ind in range(1, n):
			one_step = prev1 + abs(height[ind] - height[ind - 1])
			two_step = 10000
			if ind - 2 >= 0:
				two_step = prev2 + abs(height[ind] - height[ind - 2])
			prev2 = prev1
			prev1 = min(one_step, two_step)
		return prev1


import sys

class Solution:

	def minimumEnergy(self, height, n):
		dp = dict()
		dp[0] = 0
		for i in range(1, n):
			left = dp[i - 1] + abs(height[i] - height[i - 1])
			right = left
			if i > 1:
				right = dp[i - 2] + abs(height[i] - height[i - 2])
			dp[i] = min(left, right)
		return dp[n - 1]


class Solution:

	def minimumEnergy(self, height, n):
		dp = [0] * n
		for i in range(1, n):
			if i < 2:
				dp[i] = abs(height[i - 1] - height[i]) + dp[i - 1]
			else:
				dp[i] = min(abs(height[i - 1] - height[i]) + dp[i - 1], abs(height[i - 2] - height[i]) + dp[i - 2])
		return dp[-1]


import sys

class Solution:

	def minimumEnergy(self, height, n):
		prev2 = prev1 = 0
		for i in range(1, n):
			left = abs(height[i] - height[i - 1]) + prev1
			right = sys.maxsize
			if i > 1:
				right = abs(height[i] - height[i - 2]) + prev2
			prev2 = prev1
			prev1 = min(left, right)
		return prev1


import sys
import math

class Solution:

	def minimumEnergy(self, height, n):
		n = len(height)
		dp = [-1 for _ in range(n)]
		dp[0] = 0
		for ind in range(1, n):
			jumpTwo = float('inf')
			jumpOne = dp[ind - 1] + abs(height[ind] - height[ind - 1])
			if ind > 1:
				jumpTwo = dp[ind - 2] + abs(height[ind] - height[ind - 2])
			dp[ind] = min(jumpOne, jumpTwo)
		return dp[n - 1]


class Solution:

	def minEnergy(self, height, index, dp):
		if index == 0:
			return 0
		if dp[index] != -1:
			return dp[index]
		jumpOneStep = abs(height[index] - height[index - 1]) + self.minEnergy(height, index - 1, dp)
		jumpTwoStep = 99999
		if index > 1:
			jumpTwoStep = abs(height[index] - height[index - 2]) + self.minEnergy(height, index - 2, dp)
		dp[index] = min(jumpOneStep, jumpTwoStep)
		return min(jumpOneStep, jumpTwoStep)

	def minimumEnergy(self, height, n):
		first = 0
		if n == 1:
			return first
		second = abs(height[1] - height[0])
		for i in range(2, n):
			fs = second + abs(height[i] - height[i - 1])
			ss = first + abs(height[i] - height[i - 2])
			ans = min(fs, ss)
			first = second
			second = ans
		return second


class Solution:

	def minEnergy(self, height, index, dp):
		if index == 0:
			return 0
		if dp[index] != -1:
			return dp[index]
		jumpOneStep = abs(height[index] - height[index - 1]) + self.minEnergy(height, index - 1, dp)
		jumpTwoStep = 99999
		if index > 1:
			jumpTwoStep = abs(height[index] - height[index - 2]) + self.minEnergy(height, index - 2, dp)
		dp[index] = min(jumpOneStep, jumpTwoStep)
		return min(jumpOneStep, jumpTwoStep)

	def minimumEnergy(self, height, n):
		table = [0 for i in range(n)]
		for index in range(1, n):
			jumpOneStep = table[index - 1] + abs(height[index] - height[index - 1])
			jumpTwoStep = 999999
			if index > 1:
				jumpTwoStep = table[index - 2] + abs(height[index] - height[index - 2])
			table[index] = min(jumpOneStep, jumpTwoStep)
		return table[n - 1]


class Solution:

	def minimumEnergy(self, height, n):

		def recursive(ind, prev):
			if ind >= n:
				return 0
			energy = 0
			for ind in range(1, n):
				one_pick = abs(height[ind] - height[ind - 1]) + dp[ind - 1]
				two_pick = 10 ** 9
				if ind > 1:
					two_pick = abs(height[ind] - height[ind - 2]) + dp[ind - 2]
				dp[ind] = min(one_pick, two_pick)
			return dp[ind]
		dp = [0 for j in range(n + 1)]
		return recursive(0, -1)


class Solution:

	def minimumEnergy(self, height, n):
		prev1 = prev2 = 0
		for i in range(1, n):
			fs = prev1 + abs(height[i - 1] - height[i])
			if i > 1:
				ss = prev2 + abs(height[i - 2] - height[i])
			else:
				ss = 100000000
			curr = min(fs, ss)
			prev2 = prev1
			prev1 = curr
		return prev1


class Solution:

	def minimumEnergy(self, a, n):
		if n == 1:
			return 0
		inf = float('inf')
		dp = [inf] * (n + 1)
		dp[0] = 0
		for i in range(1, n):
			dp[i] = dp[i - 1] + abs(a[i] - a[i - 1])
			if i - 2 >= 0:
				dp[i] = min(dp[i], dp[i - 2] + abs(a[i] - a[i - 2]))
		return dp[n - 1]


import sys

class Solution:

	def minimumEnergy(self, height, n):
		prev1 = 0
		prev2 = 0
		if n == 1:
			return 0
		else:
			for i in range(1, n):
				jumptwo = sys.maxsize
				onejump = prev1 + abs(height[i] - height[i - 1])
				if i > 1:
					jumptwo = prev2 + abs(height[i] - height[i - 2])
				cur_i = min(onejump, jumptwo)
				prev2 = prev1
				prev1 = cur_i
			return cur_i


class Solution:

	def minimumEnergy(self, height, n):
		dp = [-1 for i in range(n)]
		dp[0] = 0
		for i in range(1, n):
			jumptwo = float('inf')
			onejump = dp[i - 1] + abs(height[i] - height[i - 1])
			if i > 1:
				jumptwo = dp[i - 2] + abs(height[i] - height[i - 2])
			dp[i] = min(onejump, jumptwo)
		return dp[n - 1]


class Solution:

	def minimumEnergy(self, height, n):
		prev1 = 0
		prev2 = -1
		for i in range(1, n):
			one = prev1 + abs(height[i - 1] - height[i])
			if i <= 1:
				prev2 = prev1
				prev1 = one
				continue
			two = prev2 + abs(height[i - 2] - height[i])
			prev2 = prev1
			prev1 = min(two, one)
		return prev1

	def rec(self, H, n, dp):
		if n == 0:
			return 0
		one = abs(H[n] - H[n - 1])
		if dp[n - 1] != -1:
			one += dp[n - 1]
		else:
			val = self.rec(H, n - 1, dp)
			dp[n - 1] = val
			one += val
		if n <= 1:
			return one
		two = abs(H[n] - H[n - 2])
		if dp[n - 2] != -1:
			two += dp[n - 2]
		else:
			val = self.rec(H, n - 2, dp)
			dp[n - 2] = val
			two += val
		return min(one, two)


class Solution:

	def minimumEnergy(self, height, n):
		if n == 1:
			return 0
		first = 0
		second = abs(height[1] - height[0])
		for i in range(2, n):
			(first, second) = (second, min(first + abs(height[i] - height[i - 2]), second + abs(height[i] - height[i - 1])))
		return second


class Solution:

	def minimumEnergy(self, height, n):
		prev2 = 0
		prev1 = 0
		for i in range(1, n):
			step2 = float('inf')
			step1 = prev1 + abs(height[i] - height[i - 1])
			if i > 1:
				step2 = prev2 + abs(height[i] - height[i - 2])
			curr = min(step1, step2)
			prev2 = prev1
			prev1 = curr
		return prev1


class Solution:

	def minimumEnergy(self, height, n):
		dp = [-1] * n
		dp[0] = 0
		step2 = float('inf')
		for i in range(1, n):
			step1 = dp[i - 1] + abs(height[i] - height[i - 1])
			if i > 1:
				step2 = dp[i - 2] + abs(height[i] - height[i - 2])
			dp[i] = min(step1, step2)
		return dp[n - 1]


class Solution:

	def minimumEnergy(self, height, n):
		prev1 = 0
		prev2 = 0
		for i in range(1, n):
			fm = prev1 + abs(height[i] - height[i - 1])
			sm = 10 ** 8
			if i > 1:
				sm = prev2 + abs(height[i] - height[i - 2])
			curr = min(fm, sm)
			prev2 = prev1
			prev1 = curr
		return prev1


class Solution:

	def minimumEnergy(self, height, n):
		li = []
		if n == 0 or n == 1:
			return 0
		for i in range(0, n):
			li.append(0)
		li[0] = 0
		li[1] = abs(height[1] - height[0])
		for i in range(2, n):
			left = li[i - 1] + abs(height[i] - height[i - 1])
			right = li[i - 2] + abs(height[i] - height[i - 2])
			li[i] = min(left, right)
		return li[n - 1]


class Solution:

	def minimumEnergy(self, height, n):
		prev = 0
		prev2 = 0
		for idx in range(1, n):
			left = prev + abs(height[idx - 1] - height[idx])
			if idx > 1:
				right = prev2 + abs(height[idx - 2] - height[idx])
			else:
				right = float('inf')
			curr = min(left, right)
			prev2 = prev
			prev = curr
		return prev


import sys
sys.setrecursionlimit(1500)

class Solution:

	def minimumEnergy(self, height, n):
		dp = [-1] * (n + 1)
		dp[0] = 0
		for idx in range(1, n):
			left = dp[idx - 1] + abs(height[idx - 1] - height[idx])
			if idx > 1:
				right = dp[idx - 2] + abs(height[idx - 2] - height[idx])
			else:
				right = float('inf')
			dp[idx] = min(left, right)
		return dp[n - 1]


import sys

class Solution:

	def minimumEnergy(self, height, n):
		dp = [-1] * n
		dp[0] = 0
		for i in range(1, n):
			jumpTwo = sys.maxsize
			jumpOne = dp[i - 1] + abs(height[i] - height[i - 1])
			if i > 1:
				jumpTwo = dp[i - 2] + abs(height[i] - height[i - 2])
			dp[i] = min(jumpOne, jumpTwo)
		return dp[n - 1]


class Solution:

	def minimumEnergy(self, height, n):
		prev2 = 0
		curr = 0
		if n == 1:
			return 0
		prev = abs(height[1] - height[0])
		if n == 2:
			return prev
		for i in range(2, n):
			curr = min(abs(height[i] - height[i - 1]) + prev, abs(height[i] - height[i - 2]) + prev2)
			prev2 = prev
			prev = curr
		return curr


class Solution:

	def minimumEnergy(self, height, n):
		prev1 = 0
		prev2 = 0
		for i in range(1, n):
			left = prev1 + abs(height[i] - height[i - 1])
			right = 1000000000.0
			if i > 1:
				right = prev2 + abs(height[i] - height[i - 2])
			curr = min(left, right)
			prev2 = prev1
			prev1 = curr
		return prev1


class Solution:

	def minimumEnergy(self, height, n):
		i = n - 1
		dp = [0] * n
		for i in range(1, n):
			r = 10 ** 9 + 7
			l = dp[i - 1] + abs(height[i] - height[i - 1])
			if i > 1:
				r = dp[i - 2] + abs(height[i] - height[i - 2])
			dp[i] = min(l, r)
		return dp[-1]


import sys

class Solution:

	def f(self, n, height):
		prev = 0
		prev2 = 0
		for i in range(1, n):
			jump2 = sys.maxsize
			jump1 = prev + abs(height[i] - height[i - 1])
			if i > 1:
				jump2 = prev2 + abs(height[i] - height[i - 2])
			curr = min(jump1, jump2)
			prev2 = prev
			prev = curr
		return prev

	def minimumEnergy(self, height, n):
		return self.f(n, height)


class Solution:

	def minimumEnergy(self, height, n):
		memo = {}
		return self.tab_min_energy_path(0, n - 1, height, memo)

	def min_energy_path(self, curr_index, target_index, height, memo):
		if curr_index == target_index:
			return 0
		if memo.get(curr_index) != None:
			return memo.get(curr_index)
		one_step_cost = abs(height[curr_index] - height[curr_index + 1])
		take_one_step = one_step_cost + self.min_energy_path(curr_index + 1, target_index, height, memo)
		take_two_step = float('inf')
		if curr_index <= target_index - 2:
			two_step_cost = abs(height[curr_index] - height[curr_index + 2])
			take_two_step = two_step_cost + self.min_energy_path(curr_index + 2, target_index, height, memo)
		memo[curr_index] = min(take_one_step, take_two_step)
		return memo.get(curr_index)

	def tab_min_energy_path(self, curr_index, target_index, height, memo):
		memo[target_index] = 0
		for index in range(target_index - 1, curr_index - 1, -1):
			one_step_cost = abs(height[index] - height[index + 1])
			take_one_step = one_step_cost + memo[index + 1]
			take_two_step = float('inf')
			if index <= target_index - 2:
				two_step_cost = abs(height[index] - height[index + 2])
				take_two_step = two_step_cost + memo[index + 2]
			memo[index] = min(take_one_step, take_two_step)
		return memo.get(curr_index)


class Solution:

	def minimumEnergy(self, height, n):
		k = 2
		dp = [-1] * n
		dp[0] = 0
		for i in range(1, n):
			minerg = 10000000000.0
			for j in range(1, k + 1):
				if i - j >= 0:
					curr = dp[i - j] + abs(height[i] - height[i - j])
					minerg = min(curr, minerg)
			dp[i] = minerg
		return dp[n - 1]


class Solution:

	def minimumEnergy(self, height, n):
		dp = [-1] * n
		dp[0] = 0
		if n == 1:
			return dp[n - 1]
		dp[1] = abs(height[1] - height[0])
		for i in range(2, n):
			h = height[i]
			h1 = height[i - 1]
			h2 = height[i - 2]
			onestep = abs(h - h1)
			twostep = abs(h - h2)
			dp[i] = min(onestep + dp[i - 1], twostep + dp[i - 2])
		return dp[n - 1]


class Solution:

	def minimumEnergy(self, height, n):
		n = n - 1
		m = 0
		l = abs(height[n] - height[n - 1])
		for i in range(n - 2, -1, -1):
			a = abs(height[i] - height[i + 1]) + l
			b = abs(height[i] - height[i + 2]) + m
			m = l
			l = min(a, b)
		return l


class Solution:
	dp = [-1] * 100001

	def gen(self, height, n, count):
		if count == n:
			return 0
		if count == n - 1:
			return abs(height[count + 1] - height[count])
		if count <= n and self.dp[count] != -1:
			return self.dp[count]
		a = self.gen(height, n, count + 1) + abs(height[count] - height[count + 1])
		if count + 2 <= n:
			b = self.gen(height, n, count + 2) + abs(height[count] - height[count + 2])
		else:
			b = 9999999999999
		self.dp[count] = min(a, b)
		return min(a, b)

	def minimumEnergy(self, height, n):
		n = n - 1
		dp = [-1] * (n + 1)
		dp[n] = 0
		dp[n - 1] = abs(height[n] - height[n - 1])
		for i in range(n - 2, -1, -1):
			a = abs(height[i] - height[i + 1]) + dp[i + 1]
			b = abs(height[i] - height[i + 2]) + dp[i + 2]
			dp[i] = min(a, b)
		return dp[0]


from functools import lru_cache

class Solution:

	def minimumEnergy(self, height, n):
		dp = [-1] * n
		dp[0] = 0
		for i in range(1, n):
			j2 = float('inf')
			j1 = dp[i - 1] + abs(height[i] - height[i - 1])
			if i > 1:
				j2 = dp[i - 2] + abs(height[i] - height[i - 2])
			dp[i] = min(j1, j2)
		return dp[n - 1]


from math import inf

class Solution:

	def minimumEnergy(self, height, n):
		dp = [0 for _ in range(n)]
		prev1 = 0
		prev2 = inf
		for jump in range(n - 2, -1, -1):
			one_jump = abs(height[jump] - height[jump + 1]) + prev1
			two_jump = inf
			if jump < n - 2:
				two_jump = abs(height[jump] - height[jump + 2]) + prev2
			dp[jump] = min(one_jump, two_jump)
			prev2 = prev1
			prev1 = dp[jump]
		return dp[0]


import sys
sys.setrecursionlimit(20000)

class Solution:

	def __init__(self):
		self.h = {}

	def minimumEnergy(self, height, n):
		l = [-1] * n
		l[0] = 0
		if n >= 2:
			l[1] = abs(height[1] - height[0])
		for i in range(2, n):
			l[i] = min(abs(height[i] - height[i - 1]) + l[i - 1], abs(height[i] - height[i - 2]) + l[i - 2])
		return l[n - 1]


class Solution:

	def minimumEnergy(self, arr, n):
		if n == 1 or n == 2:
			return 0 if n == 1 else abs(arr[0] - arr[1])
		ans = [0 for _ in range(n)]
		ans[0] = 0
		ans[1] = abs(arr[0] - arr[1])
		for i in range(2, n):
			diff1 = abs(arr[i] - arr[i - 1])
			diff2 = abs(arr[i] - arr[i - 2])
			ans[i] = min(diff1 + ans[i - 1], diff2 + ans[i - 2])
		return ans[n - 1]


class Solution:

	def minimumEnergy(self, height, n):
		if n == 1:
			return 0
		dp = [0] * n
		dp[0] = 0
		dp[1] = abs(height[0] - height[1])
		for i in range(len(dp) - 2):
			cost1 = dp[i] + abs(height[i] - height[i + 2])
			cost2 = dp[i + 1] + abs(height[i + 1] - height[i + 2])
			if cost1 > cost2:
				dp[i + 2] = cost2
			else:
				dp[i + 2] = cost1
		return dp[n - 1]


import sys
sys.setrecursionlimit(10000000)

class Solution:

	def minimumEnergy(self, height, n):
		dp = [0] * n
		for index in range(n - 2, -1, -1):
			one = 9999999
			if index + 1 < n:
				one = abs(height[index + 1] - height[index]) + dp[index + 1]
			two = 99999999
			if index + 2 < n:
				two = abs(height[index + 2] - height[index]) + dp[index + 2]
			dp[index] = min(one, two)
		return dp[0]


import math

class Solution:

	def minimumEnergy(self, height, n):
		n = len(height)
		prev2 = 0
		prev = 0
		for i in range(1, n):
			jumpone = prev + abs(height[i] - height[i - 1])
			jumptwo = math.inf
			if i > 1:
				jumptwo = prev2 + abs(height[i] - height[i - 2])
			curr = min(jumpone, jumptwo)
			prev2 = prev
			prev = curr
		return prev


import sys

class Solution:

	def minimumEnergy(self, height, n):
		prev1 = 0
		prev2 = 0
		for i in range(1, n):
			step1 = prev1 + abs(height[i] - height[i - 1])
			step2 = sys.maxsize
			if i > 1:
				step2 = prev2 + abs(height[i] - height[i - 2])
			cur = min(step1, step2)
			prev2 = prev1
			prev1 = cur
		return prev1


import sys
import math

class Solution:

	def minimumEnergy(self, height, n):
		prev = prev2 = 0
		for i in range(1, n):
			jone = abs(height[i] - height[i - 1]) + prev
			jtwo = float('inf')
			if i > 1:
				jtwo = abs(height[i] - height[i - 2]) + prev2
			curri = min(jone, jtwo)
			prev2 = prev
			prev = curri
		return prev


import sys
import math

class Solution:

	def minimumEnergy(self, height, n):
		dp = [-1 for _ in range(n + 1)]
		dp[0] = 0
		for i in range(1, n):
			jone = abs(height[i] - height[i - 1]) + dp[i - 1]
			jtwo = float('inf')
			if i > 1:
				jtwo = abs(height[i] - height[i - 2]) + dp[i - 2]
			dp[i] = min(jone, jtwo)
		return dp[n - 1]


import sys

class Solution:

	def minimumEnergy(self, arr, n):

		def calc(n):
			dp = [-1] * (n + 1)
			dp[0] = 0
			for i in range(1, n + 1):
				j1 = dp[i - 1] + abs(arr[i] - arr[i - 1])
				if i > 1:
					j2 = dp[i - 2] + abs(arr[i] - arr[i - 2])
				else:
					j2 = float('inf')
				dp[i] = min(j1, j2)
			return dp[n]
		return calc(n - 1)


class Solution:

	def f(self, j, arr, n, dp):
		dp[n - 1] = 0
		for j in range(n - 2, -1, -1):
			onestep = 10000000
			twostep = 10000000
			if j + 1 < n:
				onestep = abs(arr[j] - arr[j + 1]) + dp[j + 1]
			if j + 2 < n:
				twostep = abs(arr[j] - arr[j + 2]) + dp[j + 2]
			dp[j] = min(onestep, twostep)
		return dp[j]

	def minimumEnergy(self, height, n):
		dp = [-1] * n
		return self.f(0, height, n, dp)


class Solution:

	def minimumEnergy(self, height, n):
		dp = [-1] * n
		dp[0] = 0
		for i in range(1, n):
			if dp[i] == -1:
				left = dp[i - 1] + abs(height[i] - height[i - 1])
				second = 9999999
				if i > 1:
					second = dp[i - 2] + abs(height[i] - height[i - 2])
				dp[i] = min(left, second)
		return dp[n - 1]


class Solution:

	def minEnergy(self, height, index):
		if index == 0:
			return 0
		if self.dp[index] != -1:
			return self.dp[index]
		left = self.minEnergy(height, index - 1) + abs(height[index] - height[index - 1])
		right = 999999
		if index > 1:
			right = self.minEnergy(height, index - 2) + abs(height[index] - height[index - 2])
		self.dp[index] = min(left, right)
		return min(left, right)

	def minimumEnergy(self, height, n):
		dp = [0 for i in range(n)]
		for i in range(1, n):
			left = dp[i - 1] + abs(height[i] - height[i - 1])
			right = int(1000000000.0)
			if i > 1:
				right = dp[i - 2] + abs(height[i] - height[i - 2])
			dp[i] = min(left, right)
		return dp[n - 1]


from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

class Solution:

	def minimumEnergy(self, height, n):
		(prev, prev1) = (0, 0)
		for i in range(1, n):
			ans1 = prev1 + abs(height[i] - height[i - 1])
			ans2 = float('inf')
			if i > 1:
				ans2 = prev2 + abs(height[i] - height[i - 2])
			curr = min(ans1, ans2)
			prev2 = prev1
			prev1 = curr
		return prev1


from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

class Solution:

	def minimumEnergy(self, height, n):
		dp = [0 for i in range(n)]
		dp[n - 1] = 0
		for i in range(n - 2, -1, -1):
			ans1 = dp[i + 1] + abs(height[i] - height[i + 1])
			ans2 = float('inf')
			if i < n - 2:
				ans2 = dp[i + 2] + abs(height[i] - height[i + 2])
			dp[i] = min(ans1, ans2)
		return dp[0]