Tags:

• dp

2008. Maximum Earnings From Taxi

Link

class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:

        dp = [0] * (n+1)
        m = [[] for i in range(n + 5) ]


        for [v1, v2, w] in rides:
            m[v2].append([v1, w])


        res = 0

        for i in range(1, n + 1):
            dp[i] = dp[i-1]
            for [v1, w] in m[i]:
                dp[i] = max(dp[i], dp[v1] + i - v1 + w)
                res = max(res, dp[i])

        return res