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
| class Solution {
Integer[] memo;
public int mincostTickets(int[] days, int[] costs) {
memo = new Integer[days.length];
return backtrack(days, costs, 0);
}
private int backtrack(int[] days, int[] costs, int pos) {
if (pos == days.length) {
return 0;
}
if (memo[pos] != null) {
return memo[pos];
}
int minCost = Integer.MAX_VALUE;
minCost = Math.min(minCost, backtrack(days, costs, pos + 1) + costs[0]);
minCost = Math.min(minCost, backtrack(days, costs, binarySearch(days, pos + 1, days[pos] + 7)) + costs[1]);
minCost = Math.min(minCost, backtrack(days, costs, binarySearch(days, pos + 1, days[pos] + 30)) + costs[2]);
return memo[pos] = minCost;
}
private int binarySearch(int[] days, int pos, int target) {
int left = pos, right = days.length - 1, ans = days.length;
while (left <= right) {
int mid = left + (right - left) / 2;
if (days[mid] < target) {
left = mid + 1;
} else {
ans = mid;
right = mid - 1;
}
}
return ans;
}
}
|
在这样解的思路是对的. 首先是days[0], 这一天可以买单日票, 那么我们只需要求除了days[0]剩下的出行的天构成的array买票最小是多少就行了. 如果days[0]买7日票, 我们就需要看能覆盖到后面哪些出行的天, 然后求覆盖不到的天形成的array买票的最小是多少就行了. 如果days[0]买30日票也是一样, 看30日能覆盖到后面多少出行的天, 求覆盖不到的天数组成的array买票最小是多少就行了. 这三种比较哪个最小就是答案.
由于days这个array是单调递增的, 因此我们找不被覆盖的最小天是哪一天的时候就可以用binary search.
时间复杂度: O(nlogn) 一共days.length种情况, 每一种都要log(n)去找未被覆盖的天的起始是哪个. 因此是O(nlogn)
空间复杂度: O(n) 因为使用了递归以及memo这个array.
