首页 > 代码库 > 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]|
You can assume each number in the array is a positive integer and not greater than 100
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