879. Profitable Schemes

Explanation:

To solve this problem, we can use dynamic programming. We can create a 3D DP array dp[i][j][k] where i represents the number of crimes considered, j represents the total profit obtained so far, and k represents the total number of members used so far. We iterate through each crime one by one and update the DP array accordingly. The final answer will be the sum of all the DP values where the profit is at least minProfit and the total number of members used is at most n.

Algorithm:

Initialize a 3D DP array dp where dp[i][j][k] represents the number of schemes that can be chosen with i crimes considered, j total profit obtained, and k total number of members used.
Initialize dp[0][0][0] = 1, as there is 1 way to make a profit of 0 with 0 members and 0 crimes.
Iterate through each crime:
- For each crime, update the DP array based on the current crime's profit and group size.
Calculate the final result by summing up all the DP values where profit is at least minProfit and the total number of members used is at most n.
Return the final result modulo 10^9 + 7.

Time Complexity:

The time complexity of this solution is O(n * minProfit * group.length) where n is the total number of members, minProfit is the minimum profit required, and group.length is the number of crimes.

Space Complexity:

The space complexity of this solution is O(n * minProfit * group.length) for the DP array.

:

View Leetcode Problem

class Solution {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int MOD = 1000000007;
        int[][][] dp = new int[group.length + 1][n + 1][minProfit + 1];
        dp[0][0][0] = 1;

        for (int i = 1; i <= group.length; i++) {
            int g = group[i - 1];
            int p = profit[i - 1];

            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= minProfit; k++) {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (j >= g) {
                        dp[i][j][k] += dp[i - 1][j - g][Math.max(0, k - p)];
                    }
                    dp[i][j][k] %= MOD;
                }
            }
        }

        int total = 0;
        for (int j = 0; j <= n; j++) {
            total = (total + dp[group.length][j][minProfit]) % MOD;
        }

        return total;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.