879. Profitable Schemes - Explanation

1. Recursion

class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        mod = 10**9 + 7

        def dfs(i, n, p):
            if i == len(group):
                return 1 if p >= minProfit else 0

            res = dfs(i + 1, n, p)
            if n - group[i] >= 0:
                res = (res + dfs(i + 1, n - group[i], p + profit[i])) % mod

            return res

        return dfs(0, n, 0)

Time & Space Complexity

Time complexity: $O(2 ^ N)$
Space complexity: $O(N)$

Where $N$ is the size of the $group$ array.

2. Dynamic Programming (Top-Down)

class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        mod = 10**9 + 7
        dp = {}

        def dfs(i, n, p):
            if i == len(group):
                return 1 if p >= minProfit else 0
            if (i, n, p) in dp:
                return dp[(i, n, p)]

            res = dfs(i + 1, n, p)
            if n - group[i] >= 0:
                nxtP = min(p + profit[i], minProfit)
                res = (res + dfs(i + 1, n - group[i], nxtP)) % mod

            dp[(i, n, p)] = res
            return res

        return dfs(0, n, 0)

Time & Space Complexity

Time complexity: $O(N * m * n)$
Space complexity: $O(N * m * n)$

Where $N$ is the size of the $group$ array, $m$ is the given minimum profit, and $n$ is the number of group members.

3. Dynamic Programming (Bottom-Up)

class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        mod = 10**9 + 7
        N = len(group)

        dp = [[[0] * (minProfit + 1) for j in range(n + 2)] for i in range(N + 1)]
        for j in range(n + 1):
            dp[N][j][minProfit] = 1

        for i in range(N - 1, -1, -1):
            for j in range(n + 1):
                for p in range(minProfit + 1):
                    res = dp[i + 1][j][p]
                    if j >= group[i]:
                        nxtP = min(profit[i] + p, minProfit)
                        res = (res + dp[i + 1][j - group[i]][nxtP]) % mod
                    dp[i][j][p] = res

        return dp[0][n][0]

Time & Space Complexity

Time complexity: $O(N * m * n)$
Space complexity: $O(N * m * n)$

Where $N$ is the size of the $group$ array, $m$ is the given minimum profit, and $n$ is the number of group members.

4. Dynamic Programming (Space Optimized)

class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        mod = 10**9 + 7
        N = len(group)

        dp = [[0] * (minProfit + 1) for j in range(n + 2)]
        for j in range(n + 1):
            dp[j][minProfit] = 1

        for i in range(N - 1, -1, -1):
            for j in range(n, -1, -1):
                for p in range(minProfit + 1):
                    res = dp[j][p]
                    if j >= group[i]:
                        nxtP = min(profit[i] + p, minProfit)
                        res = (res + dp[j - group[i]][nxtP]) % mod
                    dp[j][p] = res

        return dp[n][0]

Time & Space Complexity

Time complexity: $O(N * m * n)$
Space complexity: $O(m * n)$

Where $N$ is the size of the $group$ array, $m$ is the given minimum profit, and $n$ is the number of group members.