mac.java

public class Solution {
    /**
     * @param A: An integer array.
     * @param target: An integer.
     */
    public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
        // write your code here
        if (A == null || A.size() == 0) {
            return 0;
        }
        
        int [][] minCount = new int[A.size()][101];
        
        for (int i = 1; i <= 100; i++) {
            minCount[0][i] = Math.abs(i - A.get(0));
        }
        
        for (int i = 1; i < A.size(); i++) {
            for (int j = 1; j <= 100; j++) {
                minCount[i][j] = Integer.MAX_VALUE;
                int min = Integer.MAX_VALUE;
                for (int pre = 1; pre <= 100; pre++) {
                    if (Math.abs(j - pre) <= target) {
                        min = Math.min(min, minCount[i - 1][pre]);
                    }
                }
                minCount[i][j] = min + Math.abs(j - A.get(i));
            }
        }
        
        int result = Integer.MAX_VALUE;
        for (int i = 1; i <= 100; i++) {
            result = Math.min(result, minCount[A.size() - 1][i]);
        }
        return result;
    }
}