There are n stones and an array of heights and Geek is standing at stone 1 and can jump to one of the following: Stone i+1, i+2, ... i+k stone and cost will be [h_{i}-h_{j}] is incurred, where j is the stone to land on. Find the minimum possible total cost incurred before the Geek reaches Stone N.
Example 1:
Input:
n = 5, k = 3
heights = {10, 30, 40, 50, 20}
Output:
30
Explanation:
Geek will follow the path 1->2->5, the total cost 
would be | 10-30| + |30-20| = 30, which is minimum
Example 2:
Input:
n = 3, k = 1
heights = {10,20,10}
Output:
20
Explanation:
Geek will follow the path 1->2->3, the total cost
would be |10 - 20| + |20 - 10| = 20.
Your Task:
You don't need to read input or print anything. Your task is to complete the function minimizeCost() which takes the array height, and integer n, and integer k and returns the minimum energy that is lost.
Expected Time Complexity: O(n*k)
Expected Space Complexity: O(n)
Constraint:
2 <= n <= 10^{5}
1 <= k <= 100
1 <= heights[i] <= 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def minimizeCost(self, height, n, k):

Solutions:
class Solution:

	def minimizeCost(self, height, n, k):
		dp = [-1] * n
		dp[0] = 0
		for ind in range(1, n):
			jumpMin = float('inf')
			for i in range(1, k + 1):
				if ind - i >= 0:
					jumpk = dp[ind - i] + abs(height[ind - i] - height[ind])
					jumpMin = min(jumpk, jumpMin)
			dp[ind] = jumpMin
		return dp[n - 1]


import sys

class Solution:

	def minimizeCost(self, height, n, k):
		dp = [-1] * n
		dp[0] = 0
		for i in range(1, n, 1):
			dp[i] = sys.maxsize
			for j in range(1, k + 1, 1):
				if i - j >= 0:
					jump = dp[i - j] + abs(height[i] - height[i - j])
				else:
					break
				dp[i] = min(dp[i], jump)
		return dp[n - 1]


class Solution:

	def minimizeCost(self, height, n, k):
		dp = [0] * n
		for i in range(1, n):
			minSteps = 1000000000.0
			for j in range(1, k + 1):
				if i - j >= 0:
					jump = dp[i - j] + abs(height[i] - height[i - j])
					minSteps = min(jump, minSteps)
				dp[i] = minSteps
		return dp[n - 1]


class Solution:

	def minimizeCost(self, height, n, k):
		dp = [-1 for i in range(n)]
		dp[0] = 0
		for i in range(1, n):
			val = 1000000
			for j in range(1, k + 1):
				if i - j < 0:
					break
				step = dp[i - j] + abs(height[i] - height[i - j])
				val = min(val, step)
				dp[i] = val
		return dp[n - 1]


class Solution:

	def minimizeCost(self, height, n, k):
		dp = [0] * n
		for i in range(n):
			temp = i - k if i - k > 0 else 0
			minn = 10 ** 5
			for j in range(temp, i):
				minn = min(abs(height[j] - height[i]) + dp[j], minn)
			dp[i] = minn if minn != 10 ** 5 else 0
		return dp[-1]


class Solution:

	def minimizeCost(self, height, n, k):
		dp = [-1 for i in range(n)]
		dp[0] = 0
		for i in range(1, n):
			int_max = 2 ** 31
			temp = int_max
			for j in range(1, k + 1):
				if i - j >= 0:
					step = dp[i - j] + abs(height[i] - height[i - j])
					temp = min(temp, step)
				else:
					break
			dp[i] = temp
		return dp[n - 1]


class Solution:

	def minimizeCost(self, height, n, k):
		dp = [-999999] * n
		dp[0] = 0
		for i in range(1, n):
			ss = 99999
			for j in range(1, k + 1):
				if i >= j:
					jump = dp[i - j] + abs(height[i] - height[i - j])
					ss = min(ss, jump)
			dp[i] = ss
		return dp[n - 1]


class Solution:

	def minCost(self, height, index, k, dp):
		if index == 0:
			return 0
		if dp[index] != -1:
			return dp[index]
		minCostValue = int(1000000000.0)
		for jump in range(1, k + 1):
			if index - jump >= 0:
				jumpValue = self.minCost(height, index - jump, k, dp) + abs(height[index] - height[index - jump])
				minCostValue = min(minCostValue, jumpValue)
		dp[index] = minCostValue
		return minCostValue

	def minimizeCost(self, height, n, k):
		table = [0 for i in range(n)]
		for index in range(1, n):
			minCostValue = int(1000000000.0)
			for jump in range(1, k + 1):
				if index - jump >= 0:
					jumpValue = table[index - jump] + abs(height[index] - height[index - jump])
					minCostValue = min(minCostValue, jumpValue)
			table[index] = minCostValue
		return table[n - 1]


class Solution:

	def minimizeCost(self, nums, n, k):
		if n == 1:
			return 0
		dp = [float('inf')] * n
		dp[0] = 0
		dp[1] = abs(nums[1] - nums[0])
		if n > 2:
			for i in range(2, n):
				j = k
				x = i - 1
				while x >= 0 and j > 0:
					dp[i] = min(dp[i], dp[x] + abs(nums[i] - nums[x]))
					x -= 1
					j -= 1
		return dp[n - 1]


class Solution:

	def minimizeCost(self, height, n, k):
		dp = [-1] * n
		dp[0] = 0
		for i in range(1, n):
			mmStep = float('inf')
			for j in range(1, k + 1):
				if i - j >= 0:
					jump = dp[i - j] + abs(height[i] - height[i - j])
					mmStep = min(mmStep, jump)
			dp[i] = mmStep
		return dp[n - 1]

	def rec(self, H, n, k, dp):
		if n == 0:
			return 0
		if dp[n] != -1:
			return dp[n]
		mmStep = float('inf')
		for i in range(1, k + 1):
			if n - i >= 0:
				jump = self.rec(H, n - i, k, dp) + abs(H[n] - H[n - i])
				mmStep = min(mmStep, jump)
		dp[n] = mmStep
		return mmStep


import sys

def minsteps(height, dp, n, k):
	dp[0] = 0
	for i in range(1, n):
		msteps = sys.maxsize
		for j in range(1, k + 1):
			if i - j >= 0:
				jump = dp[i - j] + abs(height[i] - height[i - j])
				msteps = min(jump, msteps)
		dp[i] = msteps
	return dp[n - 1]

class Solution:

	def minimizeCost(self, height, n, k):
		dp = [-1 for _ in range(n)]
		return minsteps(height, dp, n, k)


from math import inf

class Solution:

	def minimizeCost(self, height, n, k):
		if n == 1:
			return 0
		tabarray = [inf] * n
		tabarray[0] = 0
		tabarray[1] = abs(height[1] - height[0])
		for i in range(2, n):
			tabarray[i] = inf
			for j in range(1, k + 1):
				if i - j < 0:
					break
				tabarray[i] = min(tabarray[i], tabarray[i - j] + abs(height[i] - height[i - j]))
		return tabarray[n - 1]


import sys

class Solution:

	def minimizeCost(self, height, n, k):
		dp = [-1] * n
		dp[0] = 0
		for i in range(1, n):
			minSteps = float('inf')
			for j in range(1, k + 1):
				if i - j >= 0:
					minSteps = min(minSteps, dp[i - j] + abs(height[i] - height[i - j]))
				else:
					break
			dp[i] = minSteps
		return dp[-1]


class Solution:

	def minimizeCost(self, height, n, k):
		dp = [-1] * (n + 1)
		for i in range(n):
			dp[0] = 0
			Min = 10 ** 8
			for j in range(1, k + 1):
				if i - j >= 0:
					ans = dp[i - j] + abs(height[i] - height[i - j])
					Min = min(ans, Min)
			dp[i] = Min
		return dp[n - 1]


class Solution:

	def minimizeCost(self, height, n, k):
		li = []
		if n == 0 or n == 1:
			return 0
		for i in range(0, n):
			li.append(0)
		li[0] = 0
		for i in range(1, n):
			min1 = li[i - 1] + abs(height[i] - height[i - 1])
			for j in range(2, k + 1):
				if i >= j:
					val = li[i - j] + abs(height[i] - height[i - j])
					if val < min1:
						min1 = val
				else:
					break
			li[i] = min1
		return li[n - 1]


class Solution:

	def minimizeCost(self, height, n, k):
		dp = [-1 for _ in range(n)]
		dp[0] = 0
		for i in range(1, n):
			minVal = 1000000
			for j in range(1, k + 1):
				if i - j >= 0:
					minVal = min(minVal, abs(height[i] - height[i - j]) + dp[i - j])
			dp[i] = minVal
		return dp[n - 1]


class Solution:

	def minimizeCost(self, height, n, k):
		memo = {}
		return self.tab_min_cost_path(0, n - 1, height, k, memo)

	def min_cost_path(self, curr_index, target_index, height, max_steps, memo):
		if curr_index == target_index:
			return 0
		if memo.get(curr_index) != None:
			return memo.get(curr_index)
		curr_min_cost_path = float('inf')
		for step in range(1, max_steps + 1):
			next_index = curr_index + step
			if next_index <= target_index:
				curr_step_cost = abs(height[curr_index] - height[next_index])
				min_step_path = curr_step_cost + self.min_cost_path(next_index, target_index, height, max_steps, memo)
				curr_min_cost_path = min(curr_min_cost_path, min_step_path)
		memo[curr_index] = curr_min_cost_path
		return memo.get(curr_index)

	def tab_min_cost_path(self, start_index, target_index, height, max_steps, memo):
		memo[target_index] = 0
		for curr_index in range(target_index - 1, start_index - 1, -1):
			curr_min_cost_path = float('inf')
			for step in range(1, max_steps + 1):
				next_index = curr_index + step
				if next_index <= target_index:
					curr_step_cost = abs(height[curr_index] - height[next_index])
					min_step_path = curr_step_cost + memo[next_index]
					curr_min_cost_path = min(curr_min_cost_path, min_step_path)
			memo[curr_index] = curr_min_cost_path
		return memo.get(start_index)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		height = list(map(int, input().split()))
		ob = Solution()
		print(ob.minimizeCost(height, n, k))