首页 > 代码库 > LintCode-Minimum Adjustment Cost

LintCode-Minimum Adjustment Cost

Given an integer array, adjust each integers so that the difference of every adjcent 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]| 

Note

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

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.

Analysis:

Since there is boundary on the value of each element, we use dp to check every possible value of every element.

Solution:

 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         if (A.size() < 2) return 0; 8      9         int[][] cost = new int[A.size()][100];10         for (int i = 0; i < 100; i++)11             cost[0][i] = Math.abs(A.get(0)-(i+1));12         13         for (int i=1;i<A.size();i++)14             for (int j=0;j<100;j++){15                 cost[i][j]=Integer.MAX_VALUE;16                 int diff = Math.abs(A.get(i)-(j+1));17                 int upper = Math.min(j+target,99);18                 int lower = Math.max(j-target,0);19                 for (int k=lower;k<=upper;k++)20                     if (cost[i-1][k]+diff<cost[i][j])21                         cost[i][j]=cost[i-1][k]+diff;22             }23         int res = Integer.MAX_VALUE;24         for (int i=0;i<100;i++)25             if (cost[A.size()-1][i]<res)26                 res = cost[A.size()-1][i];27         return res;28     }29 }

NOTE 1: we only need to use two single dimension arrays, because cost[i][j] is only related with cost[i-1][j].

NOTE 2: if we need to output the new array, we need a list of arrays to record the current array of cost[i][j], it equals to {list of cost[i][k]} + {j}.

LintCode-Minimum Adjustment Cost