LintCode 最小调整代价

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

样例

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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;
	}
}