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 isA, the array after adjustment isB, 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 than100.

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 is2and it's minimal.

Return2.

class Solution {

public:

/\*\*

 \* @param A: An integer array.

 \* @param target: An integer.

 \*/

int MinAdjustmentCost\(vector<int> A, int target\) {

    // write your code here



    int n = A.size\(\);

    vector<vector<int>> f\(2, vector<int>\(100 + 1, 0\)\);

    int ans = INT\_MAX;

    for \(int i = 1; i <= n; ++i\) {

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

            f\[i%2\]\[j\] = INT\_MAX;

            for \(int m = 100; m > 0; --m\) {

                if \(abs\(m - j\) > target\) {

                    continue;

                }

                f\[i%2\]\[j\] = min\(f\[i%2\]\[j\], f\[\(i - 1\)%2\]\[m\] + abs\(j - A\[i - 1\]\)\);

            }

        }

    }



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

        ans = min\(ans, f\[n%2\]\[i\]\);

    }



    return ans;

}

};