LintCode 最小调整代价题目分析代码

public class Solution {
    /**
     * cnblogs.com/beiyeqingteng/
     */
    public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
        if (A == null || A.size() == 0) return 0;
        int max = getMax(A);
        int[][] costs = new int[A.size()][max + 1];
        
        for (int i = 0; i < costs.length; i++) {
            for (int j = 1; j <= max; j++) {
                costs[i][j] = Integer.MAX_VALUE;
                if (i == 0) {
                    // for the first number in the array, we assume it ranges from 1 to max;
                    costs[i][j] = Math.abs(j - A.get(i));
                } else {
                    // for the number A.get(i), if we change it to j, then the minimum total cost
                    // is decided by Math.abs(j - A.get(i)) + costs[i - 1][k], and the range of
                    // k is from Math.max(1, j - target) to Math.min(j + target, max)
                    for (int k = Math.max(1, j - target); k <= Math.min(j + target, max); k++) {
                        costs[i][j] = Math.min(costs[i][j], Math.abs(j - A.get(i)) + costs[i - 1][k]);
                    }
                }
            }
        }
        
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < costs[0].length; i++) {
            min = Math.min(min, costs[costs.length - 1][i]);
        }
        return min;
    }
    
    private int getMax(ArrayList<Integer> A) {
        int max = A.get(0);
        for (int i = 1; i < A.size(); i++) {
            max = Math.max(max, A.get(i));
        }
        return max;
    }
}