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.
1import java.util.*;
2
3public class ProfitableSchemes {
4
5 public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
6 final int MOD = 1_000_000_007;
7 int length = group.length;
8 int[][][] dp = new int[length + 1][n + 1][minProfit + 1];
9 dp[0][0][0] = 1;
10 for (int i = 1; i <= length; ++i) {
11 int g = group[i - 1], p = profit[i - 1];
12 for (int j = 0; j <= n; ++j) {
13 for (int k = 0; k <= minProfit; ++k) {
14 dp[i][j][k] = dp[i - 1][j][k];
15 if (j >= g) {
16 dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - g][Math.max(0, k - p)]) % MOD;
17 }
18 }
19 }
20 }
21 int totalSchemes = 0;
22 for (int j = 0; j <= n; ++j) {
23 totalSchemes = (totalSchemes + dp[length][j][minProfit]) % MOD;
24 }
25 return totalSchemes;
26 }
27
28}This Java implementation follows the same dynamic programming strategy, using a 3D array to compute the number of schemes that can satisfy the conditions given the constraints of group and profit for each crime.