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 <stdio.h>
2#include <string.h>
3#define MOD 1000000007
4
5int profitableSchemes(int n, int minProfit, int* group, int groupSize, int* profit) {
6 int dp[groupSize + 1][n + 1][minProfit + 1];
7 memset(dp, 0, sizeof(dp));
8 dp[0][0][0] = 1;
9 for (int i = 1; i <= groupSize; ++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][k > p ? k - p : 0]) % MOD;
16 }
17 }
18 }
19 }
20 int totalSchemes = 0;
21 for (int j = 0; j <= n; ++j) {
22 totalSchemes = (totalSchemes + dp[groupSize][j][minProfit]) % MOD;
23 }
24 return totalSchemes;
25}The C implementation uses a similar DP approach with arrays for storage due to stack constraints in C. The code follows the same logic: updating the DP table based on crime inclusion and iterating over the number of members and profit levels.