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.
1def profitableSchemes(n, minProfit, group, profit):
2 MOD = 10**9 + 7
3 length = len(group)
4 dp = [[[0] * (minProfit + 1) for _ in range(n + 1)] for _ in range(length + 1)]
5 dp[0][0][0] = 1
6 for i in range(1, length + 1):
7 g = group[i - 1]
8 p = profit[i - 1]
9 for j in range(n + 1):
10 for k in range(minProfit + 1):
11 dp[i][j][k] = dp[i - 1][j][k]
12 if j >= g:
13 dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - g][max(0, k - p)]) % MOD
14 return sum(dp[length][j][minProfit] for j in range(n + 1)) % MODThe function `profitableSchemes` initializes a 3D dynamic programming table to track the number of schemes. It iterates over each crime, updating the possible member and profit counts. Each crime decision updates the DP table based on whether the crime is included in the solution set. The final result is obtained by summing up all combinations that meet or exceed the minimum profit using at most the total number of members.