[LeetCode]IPO

这道题第一个想法是DP，我们用DP[i][j]表示在前i个project中取k个最多能达到的capital。那我们可以推出递推公式：

• dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + profits[i - 1]), if dp[i - 1][j - 1] > capital[i - 1]
• else, dp[i][j] = dp[i - 1][j]

但是我们会发现一个问题。当我们选择第i个project的时候，我们的capital总量增加，这个时候可能之前的某一个不可选的project就变得可选了。但是根据我们的递推公式，我们是没有办法回头再去考虑这个project的。为了解决这个问题，我们可以按照capital从小到大排序，对于相同capital的project，profit多的排在前面。这样当我们考虑第i个project的时候，i前面的project能否被选就不会被第i个影响了。并且如果有多个capital相同的project，我们永远会先考虑profit最大的。我们上面的递推公式依然适用，值得一提的是这道题最后的test case是5000 * 5000的，开二维矩阵必然会MLE。我们用滚动数组优化，但是仍然会TLE。不管如何，我们把DP的代码贴出来，假设总共n个projects，选k个，时间复杂度O(k * n)，空间复杂度O(k)，代码如下：

	class Solution {
	public:
	int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
	int n = Profits.size();
	vector<int> tasks;
	for(int i = 0; i < n; ++i)tasks.push_back(i);
	auto comp = [&](const int lhs, const int rhs)
	{
	return Capital[lhs] == Capital[rhs]? Profits[lhs] > Profits[rhs]: Capital[lhs] < Capital[rhs];
	};
	//sort task index based on capital, break ties by profit
	sort(tasks.begin(), tasks.end(), comp);
	//dp[i][j] represent max capital we can by select j projects in first i given choices
	//projects are sort from low to high based on its capital
	//j is always smaller than or equal to i
	//dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + profits[i], if project[i] can be selected based on dp[i - 1][j - 1]
	//otherwsise, dp[i][j] = dp[i - 1][j]
	k = min(k, n);
	vector<vector<int>> dp(2, vector<int>(k + 1, 0));
	//init
	dp[0][0] = W;
	dp[1][0] = W;
	int e = 1;
	for(int i = 1; i <= n; ++i, e ^= 1)
	{
	int idx = tasks[i - 1];
	for(int j = 1; j <= k; ++j)
	{
	dp[e][j] = dp[e ^ 1][j];
	if(dp[e ^ 1][j - 1] >= Capital[idx])
	dp[e][j] = max(dp[e][j], dp[e ^ 1][j - 1] + Profits[idx]);
	}
	}
	return dp[e ^ 1][k];
	}
	};

view raw IPO_dp.cpp hosted with ❤ by GitHub

看了下discussion发现全是greedy的解法，发现这道题用greedy的思路反而更好写。具体的做法是，对于所有满足当前capital的projects，我们永远选profit最多的那个。之后更新capital和下一次available的projects，重复一直到我们选齐k个。证明也很简单，对于k = 1的情况，显而易见是成立的。假设k = i成立，那么对于k = i + 1，鉴于我们之前选的i - 1个projects已经使capital最大了，那么对应的所有available的project也就无法更多了，在这里面选profit最大的和当前capital相加，显然就是k = i + 1情况下的最大capital。Greedy的代码可以AC，时间复杂度O(n log n)，空间复杂度O(n)，代码如下：

	class Solution {
	public:
	int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
	int n = Profits.size();
	vector<int> tasks;
	for(int i = 0; i < n; ++i)tasks.push_back(i);
	auto comp = [&](const int lhs, const int rhs)
	{
	return Capital[lhs] == Capital[rhs]? Profits[lhs] > Profits[rhs]: Capital[lhs] < Capital[rhs];
	};
	//sort task index based on capital, break ties by profit
	sort(tasks.begin(), tasks.end(), comp);
	//greedy, always take max profit one in qualified projects
	priority_queue<int> pq;
	int nextIdx = 0;
	k = min(k, n);
	while(k--)
	{
	while(nextIdx < n && Capital[tasks[nextIdx]] <= W)
	pq.push(Profits[tasks[nextIdx++]]);
	if(pq.empty())break;
	int profit = pq.top();
	pq.pop();
	W += profit;
	}
	return W;
	}
	};

view raw IPO_greedy.cpp hosted with ❤ by GitHub