879.md

879 Profitable Schemes

Description

link

---

Solution

dp[i][j] : the count of schemes with i profit and j members.

Recrusive :

• dp[i + p][j + g] += dp[i][j]) if i + p < P
• dp[P][j + g] += dp[i][j]) if i + p >= P

Initial : dp[0][0] = 1

---

Code

Complexity T : O(PGK) M : O(GP)

class Solution:
    def profitableSchemes(self, G, P, group, profit):
        """
        :type G: int
        :type P: int
        :type group: List[int]
        :type profit: List[int]
        :rtype: int
        """
        dp = [[0] * (G + 1) for _ in range(P + 1)]      
        """
        dp[i][j] means the count of schemes with i profit and j members. 
        dp[i + p][j + g] += dp[i][j]) if i + p < P
        dp[P][j + g] += dp[i][j]) if i + p >= P
        """
        dp[0][0] = 1
        for g, p in zip(group, profit):
            for i in range(P, -1, -1):
                for j in range(G - g, -1, -1):
                    dp[min(P, p + i)][g + j] += dp[i][j]
        
        return sum(dp[P]) % 1000000007