---
# System prepended metadata

title: 2830. Maximize the Profit as the Salesman
tags: [Leetcode, Dynamic Programming, Medium]

---

Link: https://leetcode.com/problems/maximize-the-profit-as-the-salesman/description/
## 思路
We can sort by end, but we can also use bucket sort
```dp[i]``` means the maximum golds for i first house

Firstly we itearate offers,
and arange offers in a list ```m```,
where ```m[end]``` is the list of offers ending at end.

Secondly we go through end from ```1``` to ```n```,
For each end,
we initialize ```dp[end]=dp[end - 1]```,
since we can remain the endth house.
Then we check each offer ending at end,
we update ```dp[end] = max(dp[end], dp[start] + gold)```

Finally we return ```dp[n]``` as result.
## Code
$O(m+n)$
```python=
class Solution:
    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
        dp = [0]*(n+1)
        endMap = [[] for _ in range(n)]
        for start, end, gold in offers:
            endMap[end].append([start, gold])
        for end in range(1, n+1):
            dp[end] = dp[end-1]
            for start, gold in endMap[end-1]:
                dp[end] = max(dp[end], dp[start]+gold)
        return dp[n]
```