Sponsored
Sponsored
This approach leverages dynamic programming to efficiently determine the number of profitable schemes. We use a 3D DP array where dp[i][j][k] represents the number of ways to select from the first i crimes such that exactly j members are used and at least k profit is generated. We iterate over each crime and update our DP table based on whether we include the crime or not in our solution set.
Time Complexity: O(L * N * P), where L is the number of crimes, N is the max number of members, and P is minProfit. Space Complexity: O(L * N * P) due to the DP table.
1#include <vector>
2using namespace std;
3
4int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
5 const int MOD = 1e9 + 7;
6 int length = group.size();
7 vector<vector<vector<int>>> dp(length + 1, vector<vector<int>>(n + 1, vector<int>(minProfit + 1, 0)));
8 dp[0][0][0] = 1;
9 for (int i = 1; i <= length; ++i) {
10 int g = group[i - 1], p = profit[i - 1];
11 for (int j = 0; j <= n; ++j) {
12 for (int k = 0; k <= minProfit; ++k) {
13 dp[i][j][k] = dp[i - 1][j][k];
14 if (j >= g) {
15 dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - g][max(0, k - p)]) % MOD;
16 }
17 }
18 }
19 }
20 int totalSchemes = 0;
21 for (int j = 0; j <= n; ++j) {
22 totalSchemes = (totalSchemes + dp[length][j][minProfit]) % MOD;
23 }
24 return totalSchemes;
25}The C++ solution follows the same logic as the Python solution, utilizing a 3D vector to implement the dynamic programming approach. The nested loops iterate through each potential crime, member, and profit combination to update the ways to achieve the desired profit using available members.