对于给定的人数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为所有犯罪收益的和。代码如下：
这个粗糙版本的代码并过不了最后一个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)。代码如下：
No comments:
Post a Comment