[C++/Python] DP - O(M+N) - Clean & Concise
Idea\n- Let dp[i] is the maximum dollars we can get if we start at point i, where 1 <= i <= n.\n- We need to build our dp in reversed order, we iterate i in [n-
**Idea**\n- Let `dp[i]` is the maximum dollars we can get if we start at point `i`, where `1 <= i <= n`.\n- We need to build our dp in reversed order, we iterate `i` in `[n-1..1]` then,\n\t- There are 2 main options:\n\t\t- Picking up rides `{e, d}` start at point `i`, we can get maximum of `dp[i] = dp[e] + d` dollars. (Of course, we need to build rides start at `i`, let say `rideStartAt[i] = [{end, dollar}]` first)\n\t\t- Don\'t pick any ride, `dp[i] = dp[i+1]`.\n\t- Choose the maximum `dp[i]` among above options.\n- Finally, `dp[1]` is our answer.\n\n**Python 3**\n```python\nclass Solution:\n    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:\n        rideStartAt = defaultdict(list)\n        for s, e, t in rides:\n            rideStartAt[s].append([e, e - s + t])  # [end, dollar]\n\n        dp = [0] * (n + 1)\n        for i in range(n - 1, 0, -1):\n            for e, d in rideStartAt[i]:\n                dp[i] = max(dp[i], dp[e] + d)\n            dp[i] = max(dp[i], dp[i + 1])\n\n        return dp[1]\n```\n\n**C++**\n```c++\n#define pii pair<int, int>\nclass Solution {\npublic:\n    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {\n        vector<vector<pii>> rideStartAt(n);\n        for (auto& ride : rides) {\n            int s = ride[0], e = ride[1], t = ride[2];\n            rideStartAt[s].push_back({e, e - s + t});  // [end, dollar]\n        }\n        vector<long long> dp(n+1);\n        for (int i = n-1; i >= 1; --i) {\n            for (auto& [e, d] : rideStartAt[i]) {\n                dp[i] = max(dp[i], dp[e] + d);\n            }\n            dp[i] = max(dp[i], dp[i + 1]);\n        }\n        return dp[1];\n    }\n};\n```\n\n**Complexity**\n- Time: `O(M + N)`, where `N <= 10^5` is number points, `M <= 4*10^4` is length of `rides` array.\n- Space: `O(M + N)`\n\nIf you think this **post is useful**, I\'m happy if you **give a vote**. Any **questions or discussions are welcome!** Thank a lot.
[]