## Thursday, July 28, 2016

### Lintcode: Minimum Adjustment Cost - GeeksforGeeks

Find minimum adjustment cost of an array - GeeksforGeeks
Given an array of positive integers, 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] – Anew[i]| where 0 <= i <= n-1, n is size of A[] and Anew[] is the array with adjacent difference less that or equal to target.
Assume all elements of the array is less than constant M = 100.

http://www.cnblogs.com/EdwardLiu/p/4385819.html

for (int p=lowerRange; p<= upperRange; p++) {
res[i][j] = Math.min(res[i][j], res[i-1][p] + Math.abs(j-A.get(i-1)));
}
``` 6     public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
7         // write your code here
8         int[][] res = new int[A.size()+1][100];
9         for (int j=0; j<=99; j++) {
10             res[0][j] = 0;
11         }
12         for (int i=1; i<=A.size(); i++) {
13             for (int j=0; j<=99; j++) {
14                 res[i][j] = Integer.MAX_VALUE;
15                 int lowerRange = Math.max(0, j-target);
16                 int upperRange = Math.min(99, j+target);
17                 for (int p=lowerRange; p<=upperRange; p++) {
18                     res[i][j] = Math.min(res[i][j], res[i-1][p]+Math.abs(j-A.get(i-1)));
19                 }
20             }
21         }
22         int result = Integer.MAX_VALUE;
23         for (int j=0; j<=99; j++) {
24             result = Math.min(result, res[A.size()][j]);
25         }
26         return result;
27     }```
https://segmentfault.com/a/1190000004950954
``````    public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
int n = A.size();
int max = 0;
for (int i = 0; i < n; i++) {
max = Math.max(max, A.get(i));
}
int[][] d = new int[n][max+1];
for (int j = 0; j <= max; j++) {
d[0][j] = Math.abs(A.get(0) - j);
}
int curMin = 0;
for (int i = 1; i < n; i++) {
curMin = Integer.MAX_VALUE;
for (int j = 0; j <= max; j++) {
d[i][j] = Integer.MAX_VALUE;
for (int k = Math.max(0, j-target); k <= Math.min(max, j+target); k++) {
d[i][j] = Math.min(d[i][j], d[i-1][k] + Math.abs(A.get(i)-j));
curMin = Math.min(curMin, d[i][j]);
}
}
}
return curMin;
} ``````
Backpack DP problem. Three for loops.
1. For each A[i]
2. For each possible value curV  (1 … 100) that A[i] could be adjusted to.
3. For each valid value lastV (1 … 100) that A[i – 1] could be adjusted to (|curV – lastV| < target). Calculate the sum of local adjustment cost:|curV – A[i]| and the accumulative min adjustment cost for A[0 … i] saved  in minCost[lastV]
public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
if (A == null || A.size() == 0) {
return 0;
}

int curMinCost[] = new int[101]; //curMinCost[v]: the min cost in A[0..i] if A[i] is changed to v
int lastMinCost[] = new int[101]; //lastMinCost[v]: the min cost in A[0..i - 1] if A[i - 1] is changed to v

//initialize
for (int v = 1; v <= 100; v++) {
curMinCost[v] = Math.abs(v - A.get(0));
}

for (int i = 1; i < A.size(); i++) {
System.arraycopy(curMinCost, 1, lastMinCost, 1, 100);
for (int curV = 1; curV <= 100; curV++) {
curMinCost[curV] = Integer.MAX_VALUE;
for (int lastV = 1; lastV <= 100; lastV++) {
if (Math.abs(curV - lastV) > target) {
continue;
}
curMinCost[curV] = Math.min(curMinCost[curV], lastMinCost[lastV] + Math.abs(curV - A.get(i)));
}
}
}

int min = Integer.MAX_VALUE;
for (int v = 1; v <= 100; v++) {
min = Math.min(min, curMinCost[v]);
}

return min;
}

In order to minimize the adjustment cost ∑|A[i] – Anew[i]| for all index i in the array, |A[i] – Anew[i]| should be as close to zero as possible. Also, |A[i] – Anew[i+1] ]| <= Target.
This problem can be solved by dynamic programming.
Let dp[i][j] defines minimal adjustment cost on changing A[i] to j, then the DP relation is defined by –
```dp[i][j] = min{dp[i - 1][k]} + |j - A[i]|
for all k's such that |k - j| <= target
```
Here, 0 <= i < n and 0 <= j <= M where n is number of elements in the array and M = 100. We have to consider all k such that max(j – target, 0) <= k <= min(M, j + target)
Finally, the minimum adjustment cost of the array will be min{dp[n – 1][j]} for all 0 <= j <= M.

`int` `minAdjustmentCost(``int` `A[], ``int` `n, ``int` `target)`
`{`
`    ``// dp[i][j] stores minimal adjustment cost on changing`
`    ``// A[i] to j`
`    ``int` `dp[n][M + 1];`

`    ``// handle first element of array seperately`
`    ``for` `(``int` `j = 0; j <= M; j++)`
`        ``dp[0][j] = ``abs``(j - A[0]);`

`    ``// do for rest elements of the array`
`    ``for` `(``int` `i = 1; i < n; i++)`
`    ``{`
`        ``// replace A[i] to j and calculate minimal adjustment`
`        ``// cost dp[i][j]`
`        ``for` `(``int` `j = 0; j <= M; j++)`
`        ``{`
`          ``// initialize minimal adjustment cost to INT_MAX`
`          ``dp[i][j] = INT_MAX;`

`          ``// consider all k such that k >= max(j - target, 0) and`
`          ``// k <= min(M, j + target) and take minimum`
`          ``for` `(``int` `k = max(j-target,0); k <= min(M,j+target); k++)`
`             ``dp[i][j] = min(dp[i][j], dp[i - 1][k] + ``abs``(A[i] - j));`
`        ``}`
`    ``}    `

`    ``// return minimum value from last row of dp table`
`    ``int` `res = INT_MAX; `
`    ``for` `(``int` `j = 0; j <= M; j++)`
`        ``res = min(res, dp[n - 1][j]);`

`    ``return` `res;`
`}`