[LeetCode]Profitable Schemes

对于给定的人数G和每个犯罪的利益和人数要求， 我们要求获得的总利益大于等于P的犯罪集合的不同组合数。我们如果把这个问题划分成子问题，对于[0, i]的所有犯罪的选项，如果我们有g个人，获得p利益的组合数是确定的，如果我们用dp[i][g][p]来表示这个结果，我们有递推方程：

• dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - group[i]][k - profit[i]]

实现的时候，为了节省空间，我们可以用hashmap而不是开三维的矩阵。时间复杂度和空间复杂度为O(G * maxP * N)，N为犯罪的总数，G为总人数，maxP为所有犯罪收益的和。代码如下：

	class Solution {
	public:
	int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {
	const int MOD = 1000000007;
	int n = group.size();
	//dp[i][j][k] represents the ways we can get profit k
	//with j people in tasks [0, i]
	//dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - group[i]][k - profit[i]]
	unordered_map<int, unordered_map<int, unordered_map<int, int>>> dp;
	for(int i = 0; i < n; ++i)
	{
	if(i)dp[i] = dp[i - 1];
	int currG = group[i], currP = profit[i];
	if(currG <= G)++dp[i][currG][currP];
	for(auto& p1 : dp[i - 1])
	{
	int usedG = p1.first;
	if(currG <= G - usedG)
	{
	for(auto& p2 : p1.second)
	{
	int gainedProfit = p2.first;
	dp[i][currG + usedG][gainedProfit + currP] += p2.second;
	dp[i][currG + usedG][gainedProfit + currP] %= MOD;
	}
	}
	}
	}
	int res = 0;
	for(const auto& p1 : dp[n - 1])
	{
	for(const auto& p2 : p1.second)
	{
	if(p2.first >= P)
	{
	res += p2.second;
	res %= MOD;
	}
	}
	}
	return res;
	}
	};

view raw Profitable Schemes_1.cpp hosted with ❤ by GitHub

这个粗糙版本的代码并过不了最后一个test case，会TLE。那么我们需要对其某些地方进行优化，首先一个很容易想到的优化就是空间上的的，因为dp[i]永远是取决于dp[i - 1]，所以我们可以考虑用rolling array来去掉一维，这样空间上可以优化到O(maxP * G)。但是显然这对时间复杂度并没有太大的帮助。为了减少时间上的开销，我们需要继续优化G或者maxP，显然G是没有办法继续优化了。对于maxP，我们可以注意到，因为我们只关心总收益大于等于P的组合数。所以对于所有大于等于P的收益我们全归结到P就可以，所以我么不需要维护[0, maxP]的区间，我们只关心[0, P]。这样一来，时间复杂度可以降低到O(N * G * P)，而空间复杂度进一步优化为O(G * P)。代码如下：

	class Solution {
	public:
	int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {
	const int MOD = 1000000007;
	int n = group.size();
	//dp[i][j][k] represents the ways we can get profit k
	//with j people in tasks [0, i]
	//dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - group[i]][k - profit[i]]
	//rolling array to save spaces
	int e = 0;
	vector<unordered_map<int, unordered_map<int, int>>> dp(2);
	for(int i = 0; i < n; ++i, e ^= 1)
	{
	int currG = group[i], currP = profit[i];
	if(i)dp[e] = dp[e ^ 1];
	if(currG <= G)++dp[e][currG][min(P, currP)];
	for(auto& p1 : dp[e ^ 1])
	{
	int usedG = p1.first;
	if(currG <= G - usedG)
	{
	for(auto& p2 : p1.second)
	{
	//having the upperbound of newP can save time
	int gainedProfit = p2.first, newP = gainedProfit + currP >= P? P: gainedProfit + currP;
	dp[e][currG + usedG][newP] += p2.second;
	dp[e][currG + usedG][newP] %= MOD;
	}
	}
	}
	}
	int res = 0;
	for(auto& p1 : dp[e ^ 1])
	{
	res += p1.second[P];
	res %= MOD;
	}
	return res;
	}
	};

view raw Profitable Schemes_2.cpp hosted with ❤ by GitHub