题目

给一个整数数组，调整每个数的大小，使得相邻的两个数的差小于一个给定的整数target，调整每个数的代价为调整前后的差的绝对值，求调整代价之和最小是多少。

样例

对于数组[1, 4, 2, 3]和target=1，最小的调整方案是调整为[2, 3, 2, 3]，调整代价之和是2。返回2。

注意

你可以假设数组中每个整数都是正整数，且小于等于100。

解题

 比较复杂

方法一

用1 到100内的数，替换数组中的每位数字

public class Solution {    /**     * @param A: An integer array.     * @param target: An integer.     */    public static int MinAdjustmentCost(ArrayList
      
        A, int target) {        // write your code here        if (A == null) {            return 0;        }                return rec(A, new ArrayList
       
        (A), target, 0);    }        /*     * SOL 1:     * 最普通的递归方法。     * */    public static int rec(ArrayList
        
          A, ArrayList
         
           B, int target, int index) {        int len = A.size();        if (index >= len) {            // The index is out of range.            return 0;        }                int dif = 0;                int min = Integer.MAX_VALUE;                // If this is the first element, it can be from 1 to 100;        for (int i = 0; i <= 100; i++) {            if (index != 0 && Math.abs(i - B.get(index - 1)) > target) {                continue;            }                        B.set(index, i);// index位置的值更新为 i             dif = Math.abs(i - A.get(index)); // 记录差值            dif += rec(A, B, target, index + 1); // 中间迭代            min = Math.min(min, dif); // 计算最小值                        // 回溯            B.set(index, A.get(index));        }                return min;    }}
         
        
       
      

超时

方法二

定义一个数组M存储中间最优过程

M[i][j] 表示第i个位置的数换成j的最优值，j取值1 - 100

public class Solution {    /**     * @param A: An integer array.     * @param target: An integer.     */    public static int MinAdjustmentCost(ArrayList
     
       A, int target) {        // write your code here        if (A == null) {            return 0;        }        int n = A.size();        int[][] M = new int[n][101];        for(int i=0;i
      
       (A),M, target, 0);    }        public static int rec(ArrayList
       
         A, ArrayList
        
          B, int[][] M,int target, int index) {        int len = A.size();        if (index >= len) {            // The index is out of range.            return 0;        }                int dif = 0;                int min = Integer.MAX_VALUE;                // If this is the first element, it can be from 1 to 100;        for (int i = 0; i <= 100; i++) {            if (index != 0 && Math.abs(i - B.get(index - 1)) > target) {                continue;            }            if(M[index][i]!=Integer.MAX_VALUE){                dif = M[index][i];                min = Math.min(min,dif);                continue;            }            B.set(index, i);// index位置的值更新为 i             dif = Math.abs(i - A.get(index)); // 记录差值            dif += rec(A, B, M,target, index + 1); // 中间迭代                        M[index][i] = dif; // 存储中间结果                        min = Math.min(min, dif); // 计算最小值                        // 回溯            B.set(index, A.get(index));        }                return min;    }}
        
       
      
     

上面博客中还要两种方法，留着下次