Minimum Adjustment Cost

Minimum Adjustment Cost

26%

Accepted

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

Have you met this question in a real interview? 

Yes

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.

Note

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

public class Solution {

    /**

     * @param A: An integer array.

     * @param target: An integer.

     */

    public int MinAdjustmentCost(ArrayList<Integer> A, int target) {

        // write your code here

        int n = A.size();

        int[][] dp = new int[n][101];

        

        for(int i = 0; i < n; i++){

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

                if(i == 0){

                    dp[i][j] = Math.abs(A.get(i) - j);

                } else {

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

                    for(int pre = 1; pre <= 100; pre++){

                        if(Math.abs(pre - j) > target) continue;

                        dp[i][j] = Math.min(dp[i][j], dp[i-1][pre] + Math.abs(j - A.get(i)));

                    }

                }

            }

        }

        

        int res = Integer.MAX_VALUE;

        

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

            res = Math.min(dp[n-1][i], res);

        }

        return res;

    }

}