Minimum Adjustment Cost

Minimum Adjustment Cost

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

Note

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.

-------------------- thinking --------------------------------------------
http://www.cnblogs.com/yuzhangcmu/p/4153927.html
http://codeanytime.blogspot.com/2014/12/lintcode-minimum-adjustment-cost.html
----------------------- codes --------------------------------------------
class Solution {
public:
    /**
     * @param A: An integer array.
     * @param target: An integer.
     */
    int MinAdjustmentCost(vector<int> A, int target) {
        // write your code here
        int f[A.size()][101];
        for (int i = 0; i <= 100; i++) {
            f[0][i] = abs(i - A[0]);
        }
        for (int j = 1; j < A.size(); j++) {
            for (int i = 0; i <= 100; i++) {
                f[j][i] = INT_MAX;
                for (int k = 0; k <= 100; k++) {
                    //bug here
                    if (abs(i - k) > target) {
                        continue;
                    }
                    if (f[j][i] > f[j-1][k] + abs(i - A[j])) {
                        f[j][i] = f[j-1][k] + abs(i - A[j]);
                    }
                }
               
            }
        }
        int min = f[A.size()-1][0];
        for (int i = 1; i <= 100; i++) {
            if (min > f[A.size()-1][i]) {
                min = f[A.size()-1][i];
            }
        }
        return min;
    }
};