forked from DengWangBao/Leetcode-Java
-
Notifications
You must be signed in to change notification settings - Fork 0
/
GuessNumberHigherOrLowerII.java
79 lines (69 loc) · 2.84 KB
/
GuessNumberHigherOrLowerII.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
* 可参考官方文档
* https://leetcode.com/articles/guess-number-higher-or-lower-ii/
* 这题不能用二分法做了,是从最差情况中挑最好的值
*/
public class GuessNumberHigherOrLowerII {
/**
* 在[start,end]中首先挑i,最差情况是i是错的,那么cost要加i,然后再从[start,i-1]和[i+1,end]中继续挑,由于是最差情况,
* 所以我们假定每次都是错的,所以cost(start,end)=i+max(cost(start,i-1),cost(i+1,end)),i在[start,end]之间遍历,从所有
* 最差情况中找到一个最小值,这就是我们要首先猜的那个数了。
*/
/**
public int getMoneyAmount(int n) {
return getMoneyAmount(1, n);
}
// 暴力方法,时间复杂度O(n!), 空间复杂度O(n)
private int getMoneyAmount(int start, int end) {
if (start >= end) {
return 0;
}
int min = Integer.MAX_VALUE;
for (int i = start; i <= end; i++) {
int res = i + Math.max(getMoneyAmount(start, i - 1), getMoneyAmount(i + 1, end));
min = Math.min(min, res);
}
return min;
}*/
/**
// 耗时18ms,和上面思路一样,只是用了缓存,避免重复计算
public int getMoneyAmount(int n) {
int[][] dp = new int[n + 1][n + 1];
return getMoneyAmount(dp, 1, n);
}
private int getMoneyAmount(int[][] dp, int start, int end) {
if (start >= end) {
return 0;
}
if (dp[start][end] != 0) {
return dp[start][end];
}
int min = Integer.MAX_VALUE;
for (int i = start; i <= end; i++) {
int res = i + Math.max(getMoneyAmount(dp, start, i - 1), getMoneyAmount(dp, i + 1, end));
min = Math.min(min, res);
}
dp[start][end] = min;
return min;
}*/
// 注意这里len要从2开始,耗时15ms
public int getMoneyAmount(int n) {
int[][] dp = new int[n + 1][n + 1];
for (int len = 2; len <= n; len++) {
for (int start = 1; start + len - 1 <= n; start++) {
int minRes = Integer.MAX_VALUE;
// 注意这里pivot的边界,因为下面有pivot+1可能越界
for (int pivot = start; pivot < start + len - 1; pivot++) {
int res = pivot + Math.max(dp[start][pivot - 1], dp[pivot + 1][start + len - 1]);
minRes = Math.min(res, minRes);
}
dp[start][start + len - 1] = minRes;
}
}
return dp[1][n];
}
/**
* 还有一点优化,不过我没想太明白,就是选择pivot时,以(start+end)/2为起点,而不是从start,大致原因是
* 相同长度下,数字越小的序列试错成本越低,所以以左边为轴的试错成本肯定高于以右边为轴的成本。
*/
}