Minimum Adjustment Cost 91

Question

Given an integer array, adjust each integers so that the difference of every adjacent 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]|

Notice

You can assume each number in the array is a positive integer and not greater than 100.

Example

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.

Solution

mac[i][j]表示前i个元素满足要求且第i个元素为j的最小cost。

初始化：mac[1][j] = Math.abs(A[0] - j)，根据题意j在1到100之间

状态函数：

mac[i][j] = min(max[i][j], mac[i-1][k] + abs(A[i-1] - j))

对于所有在范围内的k，当第i位元素取j时，取符合要求的第i－1位元素为k的情况的最小值，其中abs(j-k)的值要小于target才能符合要求。

代码如下：

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 n = A.size();
        int[][] mac = new int[n + 1][100 + 1];

        for(int i = 1; i <= 100; i++){
            mac[1][i] = Math.abs(A.get(0) - i);
        }

        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= 100; j++){

                mac[i][j] = Integer.MAX_VALUE;

                for(int k = 1; k <= 100; k++){
                    if(Math.abs(k - j) <= target){
                        mac[i][j] = Math.min(mac[i][j], mac[i - 1][k] + Math.abs(A.get(i - 1) - j));
                    }
                }//k
            }//j
        }//i

        int min = Integer.MAX_VALUE;
        for(int i = 1; i <= 100; i++){
            min = Math.min(min, mac[n][i]);
        }

        return min;
    }
}