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]|
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.
You can assume each number in the array is a positive integer and not greater than 100.
SOLUTION 1:
这个题幸好是可以认为array里的数是不大于100的正整数，不然真不好做。
首先这题看起来问的是minimize the sum所以看起来应该相识DP。但是，DP又不好想转移方程，所以先用＊记忆化搜索＊去做这个。
也就DFS ＋ memory来做：
先来开一个result存放A[index] 变到[0-100]需要的cost，这里面大部分是不需要的，只留下跟上一位数相差target之内的数字。然后开一个helper(){}递归，然后接口需要输入的是，A数组，变化后的A数组，target，result，位置index。然后DFS的helper大致就是这样：
dfs(){
B.set(index, i);
dif = i - A.get(i);
dif = dif + dfs(...index + 1..);
result[index][i] = dif;
B.set(index, A.get(index));
}
然后加一个memory，在helper里面，就是result，记录每一个位置，每次的dif。
最后输出的结果是所有result里面的最小值。
代码：
public class Solution { /** * @param A: An integer array. * @param target: An integer. */ public int MinAdjustmentCost(ArrayList<Integer> A, int target) { if (A == null || A.size() == 0){ return 0; } int[][] result = new int[A.size()][100]; for (int i = 0; i < A.size(); i++){ for (int j = 0; j < 100; j++){ result[i][j] = Integer.MAX_VALUE; } } return helper(A, new ArrayList<Integer>(A), target, result, 0); } private int helper(ArrayList<Integer> A, ArrayList<Integer> B, int target, int[][] result, int index){ int len = A.size(); if (index >= len){ return 0; } int dif = 0; int min = Integer.MAX_VALUE; for (int i = 1; i <= 100; i++){ if (index != 0 && Math.abs(i - B.get(index - 1)) > target){ continue; } if (result[index][i - 1] != Integer.MAX_VALUE){ dif = result[index][i - 1]; min = Math.min(min, dif); continue; } B.set(index, i); dif = Math.abs(i - A.get(index)); dif = dif + helper(A, B, target, result, index + 1);//递归 min = Math.min(min, dif); result[index][i - 1] = dif;//record B.set(index,A.get(index));//回朔 } return min; } }
SOLUTION 2:
DP，九章的解法：
状态：dp[index][i] 是前index个数，调整到i需要的最小cost。
方程： dp[index][i] = min((A[index] - v) + dp[index - 1][v‘]) 其中|v - v‘| <= target
初始化：初始化max就可以了
结果：dp里的最小值
public class Solution { /** * @param A: An integer array. * @param target: An integer. */ //f(x,y) 把x转换到y距离为k之内的cost //f(x,y) = min of (f(x - 1,y‘) + |A[x-1] - y|) public int MinAdjustmentCost(ArrayList<Integer> A, int target) { if (A == null || A.size() == 0){ return 0; } int size = A.size(); int[][] dp = new int[size][101]; for (int i = 0; i < size; i++){ for (int j = 1; j <= 100; j++){ dp[i][j] = Integer.MAX_VALUE; if (i == 0){ dp[i][j] = Math.abs(j - A.get(i)); } else { for (int k = 1; k <= 100; k++){ if (Math.abs(j - k) > target){ continue; } int dif = Math.abs(A.get(i) - j) + dp[i - 1][k]; dp[i][j] = Math.min(dp[i][j], dif); } } } } int result = Integer.MAX_VALUE; for (int i = 1; i <= 100; i++){ result = Math.min(result, dp[size - 1][i]); } return result; } }
[LintCode] Minimum Adjustment Cost
原文：http://www.cnblogs.com/tritritri/p/4961768.html
