Online Judge

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]|

Solution: DP

state: f[i][v] 前i个数，第i个数调整为v，满足相邻两数<=target，所需要的最小代价

function: f[i][v] = min(f[i-1][v’] + |A[i]-v|, |v-v’| <= target)

Time Complexity: O(m*n*t) m: array size n:最大可能的数 t:required range

Space Complexity: O(m*n)

public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
    if (A == null || A.size() <= 1) {
        return 0;
    }
    int maxInt = 100;//assume each number in the array is a positive integer and not greater than 100
    int[][] minCost = new int[A.size() + 1][maxInt + 1];
    for (int i = 0; i <= maxInt; i++) {
        minCost[0][i] = 0;
    }
    for (int i = 1; i <= A.size(); i++) {
        for (int j = 0; j <= maxInt; j++) {
            int costAiToJ = Math.abs(A.get(i - 1) - j);
            int min = Integer.MAX_VALUE;
            //|k-j|<=target
            //max(0, j-target) <= k <= min(target+j, maxInt)
            for (int k = Math.max(0, j - target); k <= Math.min(target + j, maxInt); k++) {
                if (minCost[i - 1][k] + costAiToJ < min) {
                    min = minCost[i - 1][k] + costAiToJ;
                }
            }
            minCost[i][j] = min;
        }
    }
    int finalMinCost = minCost[A.size()][0];
    for (int i = 0; i <= maxInt; i++) {
        if (minCost[A.size()][i] < finalMinCost) {
            finalMinCost = minCost[A.size()][i];
        }
    }
    return finalMinCost;
}

Share