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.
1var profitableSchemes = function(n, minProfit, group, profit) {
2 const MOD = 1e9 + 7;
3 const length = group.length;
4 const dp = Array.from({length: length + 1}, () => Array.from({length: n + 1}, () => Array(minProfit + 1).fill(0)));
5 dp[0][0][0] = 1;
6 for (let i = 1; i <= length; ++i) {
7 const g = group[i - 1], p = profit[i - 1];
8 for (let j = 0; j <= n; ++j) {
9 for (let k = 0; k <= minProfit; ++k) {
10 dp[i][j][k] = dp[i - 1][j][k];
11 if (j >= g) {
12 dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - g][Math.max(0, k - p)]) % MOD;
13 }
14 }
15 }
16 }
17 let totalSchemes = 0;
18 for (let j = 0; j <= n; ++j) {
19 totalSchemes = (totalSchemes + dp[length][j][minProfit]) % MOD;
20 }
21 return totalSchemes;
22};The JavaScript implementation mirrors the dynamic programming strategy applied in other languages, employing a 3D array to compute and track the number of ways crimes can be committed while meeting the constraints.