LintCode 最小调整代价

给一个整数数组，调整每个数的大小，使得相邻的两个数的差小于一个给定的整数target，调整每个数的代价为调整前后的差的绝对值，求调整代价之和最小是多少。

样例

对于数组[1, 4, 2, 3]和target=1，最小的调整方案是调整为[2, 3, 2, 3]，调整代价之和是2。返回2。

public class Solution {
    /**
     * @param A: An integer array.
     * @param target: An integer.
     */
    public int MinAdjustmentCost(ArrayList<Integer> list, int target) {
        if(null == list || list.size() <= 0)
        {
            return 0;
        }
        
        int[][] minAdjustmentCosts = new int[list.size()][101];
        int result = Integer.MAX_VALUE;
        for(int i = 0;i <= 100;i ++) // 最大值100
        {
            minAdjustmentCosts[0][i] = Math.abs(i - list.get(0));
        }
        
        for(int i = 1;i < list.size();i++)
        {
            for(int j = 0;j <= 100;j++)
            {
                minAdjustmentCosts[i][j] = Integer.MAX_VALUE;
                int left = Math.max(j - target, 0);
                int right = Math.min(j + target, 100);
                int diff = Math.abs(j - list.get(i));
                for(int k = left;k <= right;k++)
                {
                    minAdjustmentCosts[i][j] = Math.min(minAdjustmentCosts[i][j], minAdjustmentCosts[i - 1][k] + diff); 
                }
            }
        }
        
        for(int i = 0;i <= 100;i++)
        {
            if(minAdjustmentCosts[list.size() - 1][i] < result)
            {
                result = minAdjustmentCosts[list.size() - 1][i] ;
            }
        }
        
        return result;
    }
}