1 Given an integer array, adjust each integers so that the difference of every adjcent integers are not greater than a given number target.
2
3 If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|
4
5 Note
6 You can assume each number in the array is a positive integer and not greater than 100
7
8 Example
9 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. 這道題要看出是背包問題，不容易，跟FB一面 paint house很像，比那個難一點
定義res[i][j] 表示前 i個number with 最後一個number是j，這樣的minimum adjusting cost
如果第i-1個數是j, 那麼第i-2個數隻能在[lowerRange, UpperRange]之間，lowerRange=Math.max(0, j-target), upperRange=Math.min(99, j+target),
這樣的話，transfer function可以寫成：
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)));
}
1 public class Solution {
2 /**
3 * @param A: An integer array.
4 * @param target: An integer.
5 */
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 }
28 }