contest url :
https://leetcode.cn/contest/weekly-contest-359/

2830. 销售利润最大化

很好的一道DP题
虽然本质就是普通的线性DP 但是区间的那步转化非常巧妙

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
33
34
35
36
37
38

/**
状态表示: f[i] 表示销售编号不超过i的房屋的最大盈利
    状态计算:
        考虑编号为i的房屋卖或不卖:
        不卖: f[i] = f[i - 1]
        卖: 所有endj = i 的购买请求 有 f[i] = max(f[start - 1] + gold) 
        为方便遍历先将所有end相同的购买请求用hash进行存储

 */


class Solution {
public:
    int maximizeTheProfit(int n, vector<vector<int>>& offers) {
        // 先存储end 相同的offer
        // end -> <start,gold>
        unordered_map<int,vector<pair<int,int>>>hash;
        for(auto &offer: offers){
            auto &s = offer[0], &e = offer[1], &g = offer[2];
            // cout <<s << ' ' << e << ' ' << g << endl;
            hash[e].emplace_back(s,g);
        }            
        
        // f[i] 表示前i个可获得最大利润
        vector<int>f(n + 1);

        for(int e = 0 ; e < n ; e++){
            f[e + 1] = f[e];
            auto & arr = hash[e];
            for(auto &[s,g] : arr){
                f[e + 1] = max(f[e + 1], f[s] + g);
            }
        }

        return f[n];
    }
};