Lintcode - Minimum Adjustment Cost - 雯雯熊孩子 - 博客频道 - CSDN.NET
d[i][j] 代表第i个数调整到j时的最小cost。
http://www.voidcn.com/blog/martin_liang/article/p-5763525.html
Recusive with Memorization:
http://www.voidcn.com/blog/martin_liang/article/p-5763525.html
Recursive Version: Inefficient
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.
这道题要看出是背包问题，不容易，跟FB一面 paint house很像，比那个难一点
定义res[i][j] 表示前 i个number with 最后一个number是j，这样的minimum adjusting cost
如果第i-1个数是j, 那么第i-2个数只能在[lowerRange, UpperRange]之间，lowerRange=Math.max(0, j-target), upperRange=Math.min(99, j+target),
这样的话，transfer function可以写成：
for (int p=lowerRange; p<= upperRange; p++) {
res[i][j] = Math.min(res[i][j], res[i-1][p] + Math.abs(j-A.get(i-1)));
}
for each d[i][j], minimum cost = minimum cost d[i-1][j-target ... j+target] + abs(A[i]-j)
所以用三重循环，i，j，j-target...j+target
6 public int MinAdjustmentCost(ArrayList<Integer> A, int target) { 8 int[][] res = new int[A.size()+1][100]; 9 for (int j=0; j<=99; j++) { 10 res[0][j] = 0; 11 } 12 for (int i=1; i<=A.size(); i++) { 13 for (int j=0; j<=99; j++) { 14 res[i][j] = Integer.MAX_VALUE; 15 int lowerRange = Math.max(0, j-target); 16 int upperRange = Math.min(99, j+target); 17 for (int p=lowerRange; p<=upperRange; p++) { 18 res[i][j] = Math.min(res[i][j], res[i-1][p]+Math.abs(j-A.get(i-1))); 19 } 20 } 21 } 22 int result = Integer.MAX_VALUE; 23 for (int j=0; j<=99; j++) { 24 result = Math.min(result, res[A.size()][j]); 25 } 26 return result; 27 }https://segmentfault.com/a/1190000004950954
public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
int n = A.size();
int max = 0;
for (int i = 0; i < n; i++) {
max = Math.max(max, A.get(i));
}
int[][] d = new int[n][max+1];
for (int j = 0; j <= max; j++) {
d[0][j] = Math.abs(A.get(0) - j);
}
int curMin = 0;
for (int i = 1; i < n; i++) {
curMin = Integer.MAX_VALUE;
for (int j = 0; j <= max; j++) {
d[i][j] = Integer.MAX_VALUE;
for (int k = Math.max(0, j-target); k <= Math.min(max, j+target); k++) {
d[i][j] = Math.min(d[i][j], d[i-1][k] + Math.abs(A.get(i)-j));
curMin = Math.min(curMin, d[i][j]);
}
}
}
return curMin;
} public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
int n = A.size(), res = Integer.MAX_VALUE, max = res;
int[][] dp = new int[n][101];
for (int i = 0; i < n; i++) {
for (int j = 0; j <= 100; j++) {
dp[i][j] = i == 0 ? Math.abs(j - A.get(i)) : max;
}
}
for (int i = 1; i < n; i++) {
for (int j = 0; j <= 100; j++) {
for (int k = j-target; k <= j+target && k <= 100; k++) {
if (k >= 0 && dp[i-1][k] < max) dp[i][j] = Math.min(dp[i][j], dp[i-1][k]+Math.abs(j-A.get(i)));
}
}
}
for (int j = 0; j <= 100; j++) {
res = Math.min(res, dp[n-1][j]);
}
return res;
}
}public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
int n = A.size();
int max = 0;
for (int i = 0; i < n; i++) {
max = Math.max(max, A.get(i));
}
int[][] d = new int[n][max+1];
for (int j = 0; j <= max; j++) {
d[0][j] = Math.abs(A.get(0) - j);
}
int curMin = 0;
for (int i = 1; i < n; i++) {
curMin = Integer.MAX_VALUE;
for (int j = 0; j <= max; j++) {
d[i][j] = Integer.MAX_VALUE;
for (int k = Math.max(0, j-target); k <= Math.min(max, j+target); k++) {
d[i][j] = Math.min(d[i][j], d[i-1][k] + Math.abs(A.get(i)-j));
curMin = Math.min(curMin, d[i][j]);
}
}
}
return curMin;
}
}
public static int MinAdjustmentCost(ArrayList<Integer> A, int target) {
// write your code here
if (A == null || A.size() == 0) {
return 0;
}
// D[i][v]: 把index = i的值修改为v，所需要的最小花费
int[][] D = new int[A.size()][101];
int size = A.size();
for (int i = 0; i < size; i++) {
for (int j = 1; j <= 100; j++) {
D[i][j] = Integer.MAX_VALUE;
if (i == 0) {
// The first element.
D[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(j - A.get(i)) + D[i - 1][k];
D[i][j] = Math.min(D[i][j], dif);
}
}
}
}
int ret = Integer.MAX_VALUE;
for (int i = 1; i <= 100; i++) {
ret = Math.min(ret, D[size - 1][i]);
}
return ret;
}
http://blog.welkinlan.com/2015/08/14/minimum-adjustment-cost-lintcode-java/
Backpack DP problem. Three for loops.
- For each A[i]
- For each possible value curV (1 … 100) that A[i] could be adjusted to.
- For each valid value lastV (1 … 100) that A[i – 1] could be adjusted to (|curV – lastV| < target). Calculate the sum of local adjustment cost:|curV – A[i]| and the accumulative min adjustment cost for A[0 … i] saved in minCost[lastV]
public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
// write your code here
if (A == null || A.size() == 0) {
return 0;
}
int curMinCost[] = new int[101]; //curMinCost[v]: the min cost in A[0..i] if A[i] is changed to v
int lastMinCost[] = new int[101]; //lastMinCost[v]: the min cost in A[0..i - 1] if A[i - 1] is changed to v
//initialize
for (int v = 1; v <= 100; v++) {
curMinCost[v] = Math.abs(v - A.get(0));
}
for (int i = 1; i < A.size(); i++) {
System.arraycopy(curMinCost, 1, lastMinCost, 1, 100);
for (int curV = 1; curV <= 100; curV++) {
curMinCost[curV] = Integer.MAX_VALUE;
for (int lastV = 1; lastV <= 100; lastV++) {
if (Math.abs(curV - lastV) > target) {
continue;
}
curMinCost[curV] = Math.min(curMinCost[curV], lastMinCost[lastV] + Math.abs(curV - A.get(i)));
}
}
}
int min = Integer.MAX_VALUE;
for (int v = 1; v <= 100; v++) {
min = Math.min(min, curMinCost[v]);
}
return min;
}
http://www.cnblogs.com/yuzhangcmu/p/4153927.html9 public static int MinAdjustmentCost(ArrayList<Integer> A, int target) { 11 if (A == null || A.size() == 0) { 12 return 0; 13 } 15 // D[i][v]: 把index = i的值修改为v，所需要的最小花费 16 int[][] D = new int[A.size()][101]; 18 int size = A.size(); 20 for (int i = 0; i < size; i++) { 21 for (int j = 1; j <= 100; j++) { 22 D[i][j] = Integer.MAX_VALUE; 23 if (i == 0) { 24 // The first element. 25 D[i][j] = Math.abs(j - A.get(i)); 26 } else { 27 for (int k = 1; k <= 100; k++) { 28 // 不符合条件 29 if (Math.abs(j - k) > target) { 30 continue; 31 } 33 int dif = Math.abs(j - A.get(i)) + D[i - 1][k]; 34 D[i][j] = Math.min(D[i][j], dif); 35 } 36 } 37 } 38 } 40 int ret = Integer.MAX_VALUE; 41 for (int i = 1; i <= 100; i++) { 42 ret = Math.min(ret, D[size - 1][i]); 43 } 45 return ret; 46 }
Recusive with Memorization:
http://www.voidcn.com/blog/martin_liang/article/p-5763525.html
public static int MinAdjustmentCost1(ArrayList<Integer> A, int target) {
if (A == null) {
return 0;
}
return rec(A, new ArrayList<Integer>(A), target, 0);
}
public static int rec(ArrayList<Integer> A, ArrayList<Integer> 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);
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;
}
9 public static int MinAdjustmentCost2(ArrayList<Integer> A, int target) { 10 // write your code here 11 if (A == null || A.size() == 0) { 12 return 0; 13 } 15 int[][] M = new int[A.size()][100]; 16 for (int i = 0; i < A.size(); i++) { 17 for (int j = 0; j < 100; j++) { 18 M[i][j] = Integer.MAX_VALUE; 19 } 20 } 22 return rec2(A, new ArrayList<Integer>(A), target, 0, M); 23 } 25 public static int rec2(ArrayList<Integer> A, ArrayList<Integer> B, int target, int index, 26 int[][] M) { 27 int len = A.size(); 28 if (index >= len) { 29 // The index is out of range. 30 return 0; 31 } 33 int dif = 0; 34 int min = Integer.MAX_VALUE; 35 36 // If this is the first element, it can be from 1 to 100; 37 for (int i = 1; i <= 100; i++) { 38 if (index != 0 && Math.abs(i - B.get(index - 1)) > target) { 39 continue; 40 } 41 42 if (M[index][i - 1] != Integer.MAX_VALUE) { 43 dif = M[index][i - 1]; 44 min = Math.min(min, dif); 45 continue; 46 } 48 B.set(index, i); 49 dif = Math.abs(i - A.get(index)); 50 dif += rec2(A, B, target, index + 1, M); 52 min = Math.min(min, dif); 55 M[index][i - 1] = dif; 58 B.set(index, A.get(index)); 59 } 61 return min; 62 }
Recursive Version: Inefficient
5 public static int MinAdjustmentCost1(ArrayList<Integer> A, int target) { 6 // write your code here 7 if (A == null) { 8 return 0; 9 } 11 return rec(A, new ArrayList<Integer>(A), target, 0); 12 } 18 public static int rec(ArrayList<Integer> A, ArrayList<Integer> B, int target, int index) { 19 int len = A.size(); 20 if (index >= len) { 21 // The index is out of range. 22 return 0; 23 } 25 int dif = 0; 27 int min = Integer.MAX_VALUE; 29 // If this is the first element, it can be from 1 to 100; 30 for (int i = 0; i <= 100; i++) { 31 if (index != 0 && Math.abs(i - B.get(index - 1)) > target) { 32 continue; 33 } 35 B.set(index, i); 36 dif = Math.abs(i - A.get(index)); 37 dif += rec(A, B, target, index + 1); 38 min = Math.min(min, dif);// 回溯 41 B.set(index, A.get(index)); 42 } 44 return min; 45 }Read full article from Lintcode - Minimum Adjustment Cost - 雯雯熊孩子 - 博客频道 - CSDN.NET
