LC.P2008[出租车的最大盈利]

方法一：记忆化搜索

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
class Solution {
    List<int[]>[] group;
    long[] cache;

    public long maxTaxiEarnings(int n, int[][] rides) {
        cache = new long[n + 1];
        Arrays.fill(cache, -1);
        group = new List[n + 1];
        for (int[] r : rides) {
            int start = r[0], end = r[1], tip = r[2];
            if (group[end] == null) {
                group[end] = new ArrayList<>();
            }
            group[end].add(new int[]{start, end - start + tip});
        }
        return dfs(n);
    }

    private long dfs(int i) {
        if (i == 1) return 0;
        if (cache[i] != -1) return cache[i];
        // 不载在 i 下车的乘客
        long ans = dfs(i - 1);
        if (group[i] != null) {
            for (int[] r : group[i]) {
                // 载在 i 下车的乘客，剩余范围变成 [1, r[0]]
                ans = Math.max(ans, dfs(r[0]) + r[1]);
            }
        }
        return cache[i] = ans;
    }
}
  • 时间复杂度：$O(n + m)$
  • 空间复杂度：$O(n + m)$

方法二：1:1翻译成递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public long maxTaxiEarnings(int n, int[][] rides) {
        List<int[]>[] group = new List[n + 1];
        for (int[] r : rides) {
            int start = r[0], end = r[1], tip = r[2];
            if (group[end] == null) {
                group[end] = new ArrayList<>();
            }
            group[end].add(new int[]{start, end - start + tip});
        }
        long[] f = new long[n + 1];
        for (int i = 2; i <= n; ++i) {
            f[i] = f[i - 1];
            if (group[i] != null) {
                for (int[] r : group[i]) {
                    f[i] = Math.max(f[i], f[r[0]] + r[1]);
                }
            }
        }
        return f[n];
    }
}
  • 时间复杂度：$O(n + m)$
  • 空间复杂度：$O(n + m)$