## Saturday, June 25, 2016

### 最大半径问题 - James Pan - 博客频道 - CSDN.NET

class SolutionDFS {
private int max = 0;
public SolutionDFS(int[] nums, int k) {
find(nums, 0, 0, k, 0);
}
private void find(int[] nums, int from, int step, int k, int min) {
if (step == k) {
max = Math.max(max,  min);
} else if (step == 0) {
find(nums, 1, step + 1, k, Integer.MAX_VALUE);
} else if (step == k - 1) {
find(nums, nums.length, step + 1, k, Math.min(min, nums[nums.length - 1] - nums[from - 1]));
} else if (min > max) {
for(int i = from; i + (k - step) <= nums.length; i++) {
find(nums, i + 1, step + 1, k, Math.min(min, nums[i] - nums[from - 1]));
}
}
}
public int getSolution() {
return max;
}
}

class SolutionRecursive {

private boolean[][] visit;
private int[][] dp;
private int[] nums;

public SolutionRecursive(int[] nums, int k) {
int n = nums.length;
this.visit = new boolean[n + 1][k + 1];
this.dp = new int[n + 1][k + 1];
this.nums = nums;
dp(n, k);
}

public int getSolution() {
int n = dp.length - 1;
int k = dp[n].length - 1;
return dp[n][k];
}

private int dp(int n, int k) {
if (visit[n][k]) return dp[n][k];
visit[n][k] = true;
if (n < k || k == 0) {
dp[n][k] = 0;
return dp[n][k];
}
if (k == 1) {
dp[n][k] = Integer.MAX_VALUE;
return dp[n][k];
}
int result = dp(n - 1, k);
for(int i = k - 1; i < n; i++) {
result = Math.max(result, Math.min(dp(i, k - 1), nums[n - 1] - nums[i - 1]));
}
dp[n][k] = result;
return result;
}
}

class SolutionIterative {
private int solution;

public SolutionIterative(int[] nums, int k) {
int[][] radius = new int[nums.length + 1][k + 1];
for(int i = 1; i <= nums.length; i++) {
for(int j = 2; j <= k; j++) {
for(int m = j - 1; m < i; m++) {
}
}
}
}

public int getSolution() {
return this.solution;
}
}