Given an integer array, adjust each integers so that the difference of every adjacent integers are not greater than a given number target.

If the array before adjustment is **A**, the array after adjustment is **B**, you should minimize the sum of `|A[i]-B[i]|`

**Example**

Given `[1,4,2,3]`

and target = `1`

, one of the solutions is `[2,3,2,3]`

, the adjustment cost is `2`

and it’s minimal.

Return `2`

.

**Note**

You can assume each number in the array is a positive integer and not greater than `100`

.

Solution: DP

state: f[i][v] 前i个数，第i个数调整为v，满足相邻两数<=target，所需要的最小代价

function: f[i][v] = min(f[i-1][v’] + |A[i]-v|, |v-v’| <= target)

Time Complexity: O(m*n*t) m: array size n:最大可能的数 t:required range

Space Complexity: O(m*n)

public int MinAdjustmentCost(ArrayList<Integer> A, int target) { if (A == null || A.size() <= 1) { return 0; } int maxInt = 100;//assume each number in the array is a positive integer and not greater than 100 int[][] minCost = new int[A.size() + 1][maxInt + 1]; for (int i = 0; i <= maxInt; i++) { minCost[0][i] = 0; } for (int i = 1; i <= A.size(); i++) { for (int j = 0; j <= maxInt; j++) { int costAiToJ = Math.abs(A.get(i - 1) - j); int min = Integer.MAX_VALUE; //|k-j|<=target //max(0, j-target) <= k <= min(target+j, maxInt) for (int k = Math.max(0, j - target); k <= Math.min(target + j, maxInt); k++) { if (minCost[i - 1][k] + costAiToJ < min) { min = minCost[i - 1][k] + costAiToJ; } } minCost[i][j] = min; } } int finalMinCost = minCost[A.size()][0]; for (int i = 0; i <= maxInt; i++) { if (minCost[A.size()][i] < finalMinCost) { finalMinCost = minCost[A.size()][i]; } } return finalMinCost; }