[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)，代码如下：

看了下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)，代码如下：