[LintCode] Minimum Adjustment Cost

Minimum Adjustment Cost

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 isB, you should minimize the sum of |A[i]-B[i]|

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.

动态规划，dp[i][j]表示把第i个数调整为j后的最小代价，状态转移方程为：

dp[i][j] = min(dp[i][j], dp[i-1][k] + abs(A[i] - j));

其中，k表示上一个数调整后的数值，范围在max(0, j - target) 与 min(100, j + target) 之间。

class Solution {
public:
    /**
     * @param A: An integer array.
     * @param target: An integer.
     */
    int MinAdjustmentCost(vector<int> A, int target) {
        // write your code here
        if (A.empty()) return 0;
        vector<vector<int>> dp(A.size(), vector<int>(101, INT_MAX));
        for (int i = 0; i <= 100; ++i) {
            dp[0][i] = abs(A[0] - i);
        }
        for (int i = 1; i < A.size(); ++i) {
            for (int j = 0; j <= 100; ++j) {
                for (int k = max(0, j - target); k <= min(100, j + target); ++k)
                    dp[i][j] = min(dp[i][j], dp[i-1][k] + abs(A[i] - j));
            }
        }
        int res = INT_MAX;
        for (int i = 0; i <= 100; ++i) {
            res = min(res, dp[A.size()-1][i]);
        }
        return res;
    }
};