LeetCode 5861. 出租車的最大盈利(DP)

Michael阿明 2021-09-19 16:23:29 阅读数:984

leetcode 出租 最大 盈利 dp

文章目錄

1. 題目

你駕駛出租車行駛在一條有 n 個地點的路上。
這 n 個地點從近到遠編號為 1 到 n ,你想要從 1 開到 n ,通過接乘客訂單盈利。
你只能沿著編號遞增的方向前進,不能改變方向。

乘客信息用一個下標從 0 開始的二維數組 rides 錶示,其中 rides[i] = [starti, endi, tipi] 錶示第 i 比特乘客需要從地點 starti 前往 endi ,願意支付 tipi 元的小費。

每一比特 你選擇接單的乘客 i ,你可以 盈利 endi - starti + tipi 元。你同時 最多 只能接一個訂單。

給你 n 和 rides ,請你返回在最優接單方案下,你能盈利 最多 多少元。

注意:你可以在一個地點放下一比特乘客,並在同一個地點接上另一比特乘客。

示例 1:
輸入:n = 5, rides = [[2,5,4],[1,5,1]]
輸出:7
解釋:我們可以接乘客 0 的訂單,獲得 5 - 2 + 4 = 7 元。
示例 2:
輸入:n = 20, rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]
輸出:20
解釋:我們可以接以下乘客的訂單:
- 將乘客 1 從地點 3 送往地點 10 ,獲得 10 - 3 + 2 = 9 元。
- 將乘客 2 從地點 10 送往地點 12 ,獲得 12 - 10 + 3 = 5 元。
- 將乘客 5 從地點 13 送往地點 18 ,獲得 18 - 13 + 1 = 6 元。
我們總共獲得 9 + 5 + 6 = 20 元。
提示:
1 <= n <= 10^5
1 <= rides.length <= 3 * 10^4
rides[i].length == 3
1 <= starti < endi <= n
1 <= tipi <= 10^5

來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/maximum-earnings-from-taxi
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。

2. 解題

  • 先初始化每個比特置到達的情况 [(起點,收入), …] 可以到達同一點的訂單
  • 遍曆每個比特置,可以不選擇到達該比特置的訂單,最大收入是前一個點的
  • 選擇到達該點的訂單,遍曆所有訂單 取最大的
class Solution:
def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
earn = [0 for _ in range(n+1)]
events = [[] for _ in range(n+1)]
for r in rides:
events[r[1]].append((r[0], r[1]-r[0]+r[2]))
for i in range(n+1):
earn[i] = earn[i-1]
for start, money in events[i]:
earn[i] = max(earn[i], earn[start]+money)
return earn[-1]

600 ms 35.3 MB Python3


我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號(Michael阿明),一起加油、一起學習進步!
Michael阿明

版权声明:本文为[Michael阿明]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/09/20210919162329128g.html