23.04.21 Today’s Leetcode

879. Profitable Schemes

DFS Approach with Dirty memoization
TLE at 39/45

class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:

        p = list(zip(group, profit))
        # p = sorted(list(zip(group, profit)), key=lambda x: x[0])
        m = len(p)
        # print(p, m)

        visited = [False] * m
        res = 0

        dp = {}

        @functools.lru_cache(None)
        def dfs(left, cur, prev):
            if left < 0:
                return 0
            if (left, cur, prev) in dp:
                return dp[(left, cur, prev)]

            # print(left, cur, visited)
            temp = 0
            if cur >= minProfit:
                temp += 1

            for i in range(prev, m):
                if visited[i]:
                    continue
                a, b = p[i]
                visited[i] = True
                temp += dfs(left - a, cur + b, i + 1)
                visited[i] = False
            
            dp[(left, cur, prev)] = temp
            return temp

        
        return dfs(n, 0, 0) % (10**9 + 7)

Bottom-Up DP

class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        m = len(group)
        dp=[[[0]*(minProfit + 1) for _ in range(n + 1)] for _ in range(m + 1)]
        for j in range(n + 1):
            dp[m][j][0] = 1

        for i in range(m - 1, -1, -1):
            for j in range(n + 1):
                for k in range(minProfit + 1):
                    dp[i][j][k] = dp[i+1][j][k]
                    if group[i] <= j:
                        dp[i][j][k] += dp[i + 1][j - group[i]][max(0, k - profit[i])]
                    dp[i][j][k] %= 10**9 + 7

        return dp[0][n][minProfit]