05 August 2008
给了一个 NxN 的数组，表示城市i是否有飞机直达城市j，又给了一个 NxK 的数组days，表示在第j周能在城市i休假的天数，让我们找出一个行程能使休假的天数最大化。
DFS. The idea is just try each possible city for every week and keep tracking the max vacation days. Time complexity O(N^K). Of course it will TLE….
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
int max = 0, N = 0, K = 0;
public int maxVacationDays(int[][] flights, int[][] days) {
N = flights.length;
K = days[0].length;
dfs(flights, days, 0, 0, 0);
return max;
}
private void dfs(int[][] f, int[][] d, int curr, int week, int sum) {
if (week == K) {
max = Math.max(max, sum);
return;
}
for (int dest = 0; dest < N; dest++) {
if (curr == dest || f[curr][dest] == 1) {
dfs(f, d, dest, week + 1, sum + d[dest][week]);
}
}
}
}
DFS with memo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int maxVacationDays(int[][] flights, int[][] days) {
int city = days.length, week = days[0].length;
int[][]memo = new int[city][week];
return helper(flights, days, 0, 0, city, week, memo);
}
public int helper(int[][] flights, int[][] days, int curWeek, int curPos,int city, int week, int[][] memo){
if(curWeek == week){
return 0;
}
if(memo[curPos][curWeek] != 0){
return memo[curPos][curWeek];
}
int res = 0;
for(int i = 0; i < city; i++){
if(curPos == i || flights[curPos][i] == 1){
res = Math.max(res, days[i][curWeek] + helper(flights, days, curWeek + 1, i, city, week, memo));
}
}
memo[curPos][curWeek] = res;
return res;
}
}
dp[i][j] stands for the max vacation days we can get in week i staying in city j. It’s obvious that dp[i][j] = max(dp[i - 1][k] + days[j][i]) (k = 0…N - 1, if we can go from city k to city j). Also because values of week i only depends on week i - 1, so we can compress two dimensional dp array to one dimension. Time complexity O(K * N * N) as we can easily figure out from the 3 level of loops.
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
public class Solution {
public int maxVacationDays(int[][] flights, int[][] days) {
int N = flights.length;
int K = days[0].length;
int[] dp = new int[N];
Arrays.fill(dp, Integer.MIN_VALUE);
dp[0] = 0;
for (int i = 0; i < K; i++) {
int[] temp = new int[N];
Arrays.fill(temp, Integer.MIN_VALUE);
for (int j = 0; j < N; j++) {
for(int k = 0; k < N; k++) {
if (j == k || flights[k][j] == 1) {
temp[j] = Math.max(temp[j], dp[k] + days[j][i]);
}
}
}
dp = temp;
}
int max = 0;
for (int v : dp) {
max = Math.max(max, v);
}
return max;
}
}