CODEWITHSUNDEEP
javaarraysdynamic-programming
nz_21
nz_21

Reputation: 7343

Minimum Adjustment Cost

I am trying to solve this 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] |. You can assume each number in the array is a positive integer and not greater than 100.

`

I see a dp solution but I don't quite understand the recurrence equation. 

public static int MinAdjustmentCost(ArrayList<Integer> A, int target) {
    // write your code here
    if (A == null || A.size() == 0) {
        return 0;
    }

    // D[i][v]: 把index = i的值修改为v，所需要的最小花费
    int[][] D = new int[A.size()][101];

    int size = A.size();

    for (int i = 0; i < size; i++) {
        for (int j = 1; j <= 100; j++) {
            D[i][j] = Integer.MAX_VALUE;
            if (i == 0) {
                // The first element.
                D[i][j] = Math.abs(j - A.get(i));
            } else {
                for (int k = 1; k <= 100; k++) {
                    // 不符合条件 
                    if (Math.abs(j - k) > target) {
                        continue;
                    }

                    int dif = Math.abs(j - A.get(i)) + D[i - 1][k];
                    D[i][j] = Math.min(D[i][j], dif);
                }
            }
        }
    }

    int ret = Integer.MAX_VALUE;
    for (int i = 1; i <= 100; i++) {
        ret = Math.min(ret, D[size - 1][i]);
    }

    return ret;
}

Could someone explain it to me?

Upvotes: 1

Views: 838

Answers (1)

Mohd
Mohd

Reputation: 5613

You need to minimize the cost of the adjustment, which is the value you increase/decrease every element such that the difference between every adjacent elements is less than or equal to target. The dp solution is to try every possible value and minimize the cost on the valid ones (when abs(A[i]-A[i-1]) <= target)

First thing is to fill the cost for adjusting first element to 1-100 which is done here:

 for (int i = 0; i < size; i++) {
        for (int j = 1; j <= 100; j++) {
            D[i][j] = Integer.MAX_VALUE; // fill with MAX_VALUE because we want to minimize
            if (i == 0) {
                // for the first element we just set the cost of adjusting A[i] to j
                D[i][j] = Math.abs(j - A.get(i));
            }

Now you have D[0][j] as the cost to adjust the first element to be j. Then for every other element, you loop again (from k = 1 to k = 100) for other elements and try to change A[i] to j. And then you check if abs(k-j) is valid (less than or equal to target) then you can adjust A[i] to be j and A[i-1] to be k so you minimize on D[i][j].

Here D[i][j] means the cost of changing A[i] to j and D[i-1][k] is the cost of changing A[i-1] to k. so for every k and j if they are valid (abs(k-j)<=target) then you add them together and minimize the value saved in D[i][j] so you can use it for next element, which is done here: 

else {
    for (int k = 1; k <= 100; k++) {
        // if abs(j-k) > target then changing A[i] to j isn't valid (when A[i-1] is k)
        if (Math.abs(j - k) > target) {
            continue;
        }
        // otherwise, calculate the the cost of changing A[i] to j and add to it the cost of changing A[i-1] to k
        int dif = Math.abs(j - A.get(i)) + D[i - 1][k];
        // minimize D[i][j]
        D[i][j] = Math.min(D[i][j], dif);
     }
}

At the end, you need to loop from 1 to 100 at the last element and check which is the minimum value over all, which is done here:

int ret = Integer.MAX_VALUE;
for (int i = 1; i <= 100; i++) {
    ret = Math.min(ret, D[size - 1][i]);
}

I think if you split the initialization code and the DP calculation code it would be easier to understand, for example:

// fill the initial values
for (int i = 0; i < size; ++i) {
    for (int j = 1; j <= 100; ++j) {
        // on the first element just save the cost of changing
        // A[i] to j
        if (i == 0) {
            DP[i][j] = abs(j-A.get(i));
        } else {
            // otherwise intialize with MAX_VALUE
            D[i][j] = Integer.MAX_VALUE;        
        }

    }
}
for (int i = 1; i < size; i++) {
    for (int j = 1; j <= 100; j++) {
        for (int k = 1; k <= 100; k++) {
            // if abs(j-k) isn't valid skip it
            if (Math.abs(j - k) > target) {
                continue;
            }
            // if it is valid, calculate the cost of changing A[i] to j
            // and add it to the cost of changing A[i-1] to k then minimize
            // over all values of j and k
            int dif = Math.abs(j - A.get(i)) + D[i - 1][k];
            D[i][j] = Math.min(D[i][j], dif);
        }
    }
}

// calculate the minimum cost at the end
int ret = Integer.MAX_VALUE;
for (int i = 1; i <= 100; i++) {
    ret = Math.min(ret, D[size - 1][i]);
}

Upvotes: 2

Related Questions