mirror of https://github.com/doocs/leetcode.git
23 lines
784 B
C++
23 lines
784 B
C++
class Solution {
|
|
public:
|
|
int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
|
|
int m = group.size();
|
|
int f[m + 1][n + 1][minProfit + 1];
|
|
memset(f, 0, sizeof(f));
|
|
for (int j = 0; j <= n; ++j) {
|
|
f[0][j][0] = 1;
|
|
}
|
|
const int mod = 1e9 + 7;
|
|
for (int i = 1; i <= m; ++i) {
|
|
for (int j = 0; j <= n; ++j) {
|
|
for (int k = 0; k <= minProfit; ++k) {
|
|
f[i][j][k] = f[i - 1][j][k];
|
|
if (j >= group[i - 1]) {
|
|
f[i][j][k] = (f[i][j][k] + f[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])]) % mod;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return f[m][n][minProfit];
|
|
}
|
|
}; |