LintCode: 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.

 
class Solution {
public:
    /**
     * @param A: An integer array.
     * @param target: An integer.
     */
    int MinAdjustmentCost(vector<int> A, int target) {
        if (A.empty()) {
            return 0;
        }
        int n = A.size();
        int ptr = 0;
        memset(dp, 0, sizeof(dp));
       
        for (int i = 0; i < n; i++) {
            int cur = A[i];
            int next = ptr ^ 1;
           
            for (int j = 1; j <= 100; j++) {
                dp[next][j] = INT_MAX;
                int diff = abs(cur - j);
                int range_l = max(1, j - target);
                int range_r = min(100, j + target);
                for (int k = range_l; k <= range_r; k++)
                    dp[next][j] = min(dp[next][j], dp[ptr][k] + diff);
            }
            ptr ^= 1;
        }
        int ans = INT_MAX;
        for (int i = 1; i <= SIZE; i++)
            ans = min(ans, dp[ptr][i]);
       
        return ans;
    }
private:
    static const int SIZE = 100;
    int dp[2][SIZE + 1];
};
 

class Solution {
public:
    /**
     * @param A: An integer array.
     * @param target: An integer.
     */
    int MinAdjustmentCost(vector<int> A, int target) {
       int N = A.size();
       int C = 100;
       vector<vector<int>> CumSum(2, vector<int>(C, 0));
       int current = 0;
       for(int i = 0; i < N; i++) {
           current = 1- current;
           int prev = 1 - current;
           for(int j = 1; j <= C; j++) {
               int upper = min(C, j + target);
               int lower = max(1, j - target);
               CumSum[current][j-1] = INT_MAX;
               for(int k = lower; k <=upper; k++) 
                   CumSum[current][j-1] = min(CumSum[current][j-1], CumSum[prev][k-1]);    
               CumSum[current][j-1] += abs(A[i] - j);
           }
       }
       
       int output = CumSum[current][0];
       for(int i = 1; i < C; i++) 
          output = min(output, CumSum[current][i]);
          
       return output;
    }
};