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.
1using System;
2
3public class Solution {
4 public int ProfitableSchemes(int n, int minProfit, int[] group, int[] profit) {
5 const int MOD = 1000000007;
6 int length = group.Length;
7 var dp = new int[length + 1, n + 1, minProfit + 1];
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, Math.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 }
26}The C# solution employs an analogous dynamic programming approach as outlined in other languages, utilizing a three-dimensional array to calculate the number of profitable schemes under the given conditions.