本文涉及知识点

C++动态规划
C++图论

LeetCode2830. 销售利润最大化

给你一个整数 n 表示数轴上的房屋数量，编号从 0 到 n - 1 。
另给你一个二维整数数组 offers ，其中 offers[i] = [starti, endi, goldi] 表示第 i 个买家想要以 goldi 枚金币的价格购买从 starti 到 endi 的所有房屋。
作为一名销售，你需要有策略地选择并销售房屋使自己的收入最大化。
返回你可以赚取的金币的最大数目。
注意 同一所房屋不能卖给不同的买家，并且允许保留一些房屋不进行出售。
示例 1：
输入：n = 5, offers = [[0,0,1],[0,2,2],[1,3,2]]
输出：3
解释：
有 5 所房屋，编号从 0 到 4 ，共有 3 个购买要约。
将位于 [0,0] 范围内的房屋以 1 金币的价格出售给第 1 位买家，并将位于 [1,3] 范围内的房屋以 2 金币的价格出售给第 3 位买家。
可以证明我们最多只能获得 3 枚金币。
示例 2：
输入：n = 5, offers = [[0,0,1],[0,2,10],[1,3,2]]
输出：10
解释：有 5 所房屋，编号从 0 到 4 ，共有 3 个购买要约。
将位于 [0,2] 范围内的房屋以 10 金币的价格出售给第 2 位买家。
可以证明我们最多只能获得 10 枚金币。

提示：
1 <= n <= 10⁵
1 <= offers.length <= 10⁵
offers[i].length == 3
0 <= starti <= endi <= n - 1
1 <= goldi <= 10³

动态规划+图论

LeetCode2008题几乎一样
将offices转为邻接表。

动态规划的状态表示

dp[i]表示处理完前i间房屋的最大价格。空间复杂度：O(n)

动态规划的填报顺序

枚举前置状态，i = 0 to n-1

动态规划的转移方程

MaxSelf(dp[i+1],dp[i])，房子i不卖。
for([next,g] : neiBo[i])
MaxSelf(dp[next+1],dp[i]+g)
总时间复杂度：O(m) m = offices.length。

动态规划的初始值

全为0

动态规划的返回值

dp.back

代码

核心代码

class CNeiBo
{
public:	
	static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) 
	{
		vector<vector<int>>  vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
			}
		}
		return vNeiBo;
	}	
	static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
	{
		vector<vector<std::pair<int, int>>> vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
			}
		}
		return vNeiBo;
	}	
	static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat)
	{
		vector<vector<int>> neiBo(neiBoMat.size());
		for (int i = 0; i < neiBoMat.size(); i++)
		{
			for (int j = i + 1; j < neiBoMat.size(); j++)
			{
				if (neiBoMat[i][j])
				{
					neiBo[i].emplace_back(j);
					neiBo[j].emplace_back(i);
				}
			}
		}
		return neiBo;
	}
};

class Solution {
		public:
			int maximizeTheProfit(int n, vector<vector<int>>& offers) {
				auto neiBo = CNeiBo::Three(n, offers, true);
				vector<int> dp(n + 1);
				for (int i = 0; i < n; i++) {
					dp[i + 1] = max(dp[i + 1], dp[i]);
					for (const auto& [next,p] : neiBo[i]) {
						dp[next + 1] = max(dp[next + 1], dp[i] + p);
					}
				}
				return dp.back();
			}
		};

单元测试

int n;
		vector<vector<int>> offers;
		TEST_METHOD(TestMethod11)
		{
			n = 5, offers = { {0,0,1},{0,2,2},{1,3,2} };
			auto res = Solution().maximizeTheProfit(n, offers);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod12)
		{
			n = 5, offers = { {0,0,1},{0,2,10},{1,3,2} };
			auto res = Solution().maximizeTheProfit(n, offers);
			AssertEx(10, res);
		}