Given an array arr[] of positive integers of size N and an integer target, replace each element in the array such that the difference between adjacent elements in the array is less than or equal to a given target. We need to minimize the adjustment cost, that is the sum of differences between new and old values. We basically need to minimize ∑|A[i]  A_{new}[i]| where 0 <= i <= n-1, n is size of A[] and A_{new}[] is the array with adjacent difference less than or equal to target.Assume all elements of the array is less than constant M = 100.
 
Example 1:
Input: N = 4, target = 1
arr[] = { 1, 3, 0, 3 }
Output: 3
Explanation: One of the possible 
solutions is [2, 3, 2, 3].
Example 2:
Input: N = 4, target = 1
arr[] = {2, 3, 2, 3}
Output: 0
Explanation: All adjacent elements 
in the input array are already less 
than equal to given target.
Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function minAdjustmentCost() that takes array arr[] , integer n, and integer target as parameters and returns the minimum adjustment cost.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{2}

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Data structures

Starter code: 



class Solution:

    def minAdjustmentCost(self, arr, n, target):

        # Your code goes here

Solutions:
class Solution:

	def minAdjustmentCost(self, A, n, target):
		M = max(A)
		dp = [[0 for i in range(M + 1)] for i in range(n)]
		for j in range(M + 1):
			dp[0][j] = abs(j - A[0])
		for i in range(1, n):
			for j in range(M + 1):
				dp[i][j] = 100000000
				for k in range(max(j - target, 0), min(M, j + target) + 1):
					dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(A[i] - j))
		res = 10000000
		for j in range(M + 1):
			res = min(res, dp[n - 1][j])
		return res


M = 100

class Solution:

	def minAdjustmentCost(self, arr, n, target):
		dp = [[float('inf') for _ in range(M + 1)] for _ in range(n)]
		for j in range(M + 1):
			dp[0][j] = abs(j - arr[0])
		for i in range(1, n):
			for j in range(M + 1):
				for k in range(max(j - target, 0), min(j + target, M) + 1):
					dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(arr[i] - j))
		res = min(dp[n - 1])
		return res


import sys

class Solution:

	def minAdjustmentCost(self, arr, n, target):
		M = 100
		dp = [[sys.maxsize for i in range(M + 1)] for i in range(n)]
		for i in range(M + 1):
			dp[0][i] = abs(arr[0] - i)
		for i in range(1, n):
			for j in range(M + 1):
				for k in range(max(0, j - target), min(M, target + j) + 1):
					dp[i][j] = min(dp[i - 1][k] + abs(j - arr[i]), dp[i][j])
		min_val = sys.maxsize
		for i in range(M + 1):
			min_val = min(dp[n - 1][i], min_val)
		return min_val
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		l = list(map(int, input().split()))
		n = l[0]
		k = l[1]
		a = list(map(int, input().split()))
		ob = Solution()
		ans = ob.minAdjustmentCost(a, n, k)
		print(ans)


class Solution:

	def minAdjustmentCost(self, arr, n, target):
		dp = [[0] * 101 for _ in range(n)]
		dp[0] = [abs(arr[0] - i) for i in range(101)]
		for i in range(1, n):
			for m in range(101):
				dp[i][m] = min([dp[i - 1][j] for j in range(m - target, m + target + 1) if 0 <= j <= 100]) + abs(m - arr[i])
		return min(dp[n - 1])