2830. 销售利润最大化

发表于 2026-01-12 分类于力扣阅读次数： Waline：本文字数： 913 阅读时长 ≈ 3 分钟

考点

划分DP
线性DP

思路

一、问题抽象与建模

给定一排编号为 \[ 0,1,2,\dots,n-1 \] 的连续房屋，以及若干个销售方案（offer）。每个销售方案可以抽象为一个三元组： \[ (s, e, g) \] 其中：

\(s\)：方案覆盖的起始房屋编号
\(e\)：方案覆盖的结束房屋编号
\(g\)：接受该方案所获得的收益

若选择一个方案 \((s,e,g)\)，则区间 \([s,e]\) 内的房屋将被整体出售，不能再与任何覆盖该区间的其他方案同时选择。

目标：在所有互不重叠的方案中，选择若干个，使得总收益最大。

该问题本质上是一个带权不相交区间选择问题，但由于区间端点均落在连续整数轴上，可进一步转化为前缀动态规划问题。

二、动态规划状态定义

定义状态函数： \[ f(i) \] 表示： 仅考虑房屋编号位于区间 \([0,\, i-1]\) 内的所有方案时，所能获得的最大收益。

说明：

\(f(0)=0\)：不考虑任何房屋时，收益为 0
最终答案为 \(f(n)\)

该定义的关键在于：状态以房屋编号的前缀为边界，而非以方案数量为边界，使得“不相交”约束自然体现在状态转移中。

三、状态转移方程

在计算 \(f(i)\) 时（\(1 \le i \le n\)），考虑两种可能：

1. 不使用任何以 \(i-1\) 结尾的方案

此时最优收益与前一状态相同： \[ f(i) = f(i-1) \]

2. 使用某个以 \(i-1\) 结尾的方案

设存在方案 \((s,\, i-1,\, g)\)，若选择该方案：

区间 \([s,\, i-1]\) 被占用
之前可接上的最优状态为 \(f(s)\)

对应收益为： \[ f(s) + g \]

3. 综合转移

综合上述两种情况，状态转移方程为： \[ f(i) = \max \left( f(i-1), \max_{(s,\, i-1,\, g)} \left\{ f(s) + g \right\} \right) \]

四、实现策略与复杂度分析

分桶思想

为了高效枚举“以 \(i-1\) 结尾的所有方案”，将所有方案按结束位置分桶：

ends[e]：存储所有结束位置为 e 的方案 \((s,g)\)

这样在计算 \(f(i)\) 时，只需遍历 ends[i-1]。

时间复杂度

每个方案仅被处理一次
总时间复杂度：

\[ O(n + m) \]

其中 \(m\) 为方案数量。

空间复杂度

状态数组 \(f\)：\(O(n)\)
分桶存储方案：\(O(m)\)

五、AC代码

class Solution {
public:
    static const int maxn = 1e5 + 5;

    int maximizeTheProfit(int n, vector<vector<int>>& offers) {
        // ends[e] 存储所有结束位置为 e 的方案
        // 每个方案以 (s, g) 的形式保存
        vector<vector<pair<int, int>>> ends(n + 1);
        for (auto& offer : offers) {
            int s = offer[0];
            int e = offer[1];
            int g = offer[2];
            ends[e].push_back({s, g});
        }

        // f[i] 表示仅考虑房屋 [0, i-1] 时的最大收益
        int f[maxn];
        f[0] = 0;

        for (int i = 1; i <= n; ++i) {
            // 情况一：不选任何以 i-1 结尾的方案
            f[i] = f[i - 1];

            // 情况二：枚举所有以 i-1 结尾的方案
            for (auto& [s, g] : ends[i - 1]) {
                // 若选方案 [s, i-1]，则可接上的最优收益为 f[s]
                f[i] = max(f[i], f[s] + g);
            }
        }

        // 最终答案：考虑所有房屋 [0, n-1] 的最优收益
        return f[n];
    }
};