0879.cpp (659B)
1 class Solution { 2 public: 3 int profitableSchemes(int n, int minProfit, const vector<int> &group, const vector<int> &profit) { 4 int dp[101][101] = {{1}}; 5 int res = 0, mod = 1e9 + 7; 6 for (int k = 0; k < group.size(); k++) { 7 int g = group[k], p = profit[k]; 8 for (int i = minProfit; i >= 0; i--) { 9 for (int j = n - g; j >= 0; j--) { 10 int &cache = dp[min(i + p, minProfit)][j + g]; 11 cache = (cache + dp[i][j]) % mod; 12 } 13 } 14 } 15 for (int x : dp[minProfit]) 16 res = (res + x) % mod; 17 return res; 18 } 19 };