DP solution for mouse and holes problem

From: Philip Yu
Sent: Thursday, October 23, 2014 4:01 PM
To: Neo Chen
Subject: RE: 今天做做这题吧

Bug来了：
int[] m7 = { 64, 82, 95, 152, 166 };
int[] h7 = { 9, 25, 28, 36, 54, 118, 119, 172, 189, 195 };
正确是28
你的是33
昨天我想错了一步，满盘皆啰嗦，这样就好了
public int min2(int[] mouse, int[] holes) {
if (mouse == null || holes == null)
return -1;
int lenM = mouse.length;
int lenH = holes.length;
if (lenM > lenH)
return -1;
Arrays.sort(mouse);
Arrays.sort(holes);
int[][] DP = new int[lenM][lenH];
DP[0][0] = Math.abs(mouse[0] - holes[0]);
int min = DP[0][0];
for (int i = 0; i < lenH; i++) {
DP[0][i] = min = Math.min(min, Math.abs(mouse[0] - holes[i]));
}
for (int i = 1; i < lenM; i++) {
DP[i][i] = Math.max(DP[i - 1][i - 1], Math.abs(mouse[i] - holes[i]));
}
for (int i = 1; i < lenM; i++) {
for (int j = i + 1; j < lenH; j++) {
DP[i][j] = Math.min(DP[i][j - 1],
Math.max(DP[i - 1][j - 1], Math.abs(mouse[i] - holes[j])));
}
}
return DP[lenM - 1][lenH - 1];
}