Problem

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

 Notice
     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.

思路

• Because we are going to change n elements in from an array with m elements to match the target, it would take O(2^n) time, cuz it is kind of combination. we can know there is some overlapping subproblems. for example in the picture
• 

    public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
        if (A == null || A.size() == 0) {
            return 0;
        }

        int n = A.size();
        int change = 100;
        int[][] dp = new int[n + 1][change + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= change; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                int min = Math.max(1, j - target);
                int max = Math.min(100, j + target);
                for (int k = min; k <= max; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + Math.abs(j - A.get(i - 1)));
                }
            }
        }

        int res = Integer.MAX_VALUE;
        for (int i = 1; i <= change; i++) {
            res = Math.min(res, dp[n][i]);
        }

        return res;
    }

滚动数组优化

reference:

http://ihuafan.com/%E7%AE%97%E6%B3%95/lintcode-dynamic-programming-summary#lintcode-91-minimum-adjustment-cost-%E6%9C%80%E5%B0%8F%E8%B0%83%E6%95%B4%E4%BB%A3%E4%BB%B7