<p>There is a group of <code>n</code> members, and a list of various crimes they could commit. The <code>i<sup>th</sup></code> crime generates a <code>profit[i]</code> and requires <code>group[i]</code> members to participate in it. If a member participates in one crime, that member can&#39;t participate in another crime.</p>

<p>Let&#39;s call a <strong>profitable scheme</strong> any subset of these crimes that generates at least <code>minProfit</code> profit, and the total number of members participating in that subset of crimes is at most <code>n</code>.</p>

<p>Return the number of schemes that can be chosen. Since the answer may be very large, <strong>return it modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 5, minProfit = 3, group = [2,2], profit = [2,3]
<strong>Output:</strong> 2
<strong>Explanation:</strong> To make a profit of at least 3, the group could either commit crimes 0 and 1, or just crime 1.
In total, there are 2 schemes.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
<strong>Output:</strong> 7
<strong>Explanation:</strong> To make a profit of at least 5, the group could commit any crimes, as long as they commit one.
There are 7 possible schemes: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2).</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code>0 &lt;= minProfit &lt;= 100</code></li>
	<li><code>1 &lt;= group.length &lt;= 100</code></li>
	<li><code>1 &lt;= group[i] &lt;= 100</code></li>
	<li><code>profit.length == group.length</code></li>
	<li><code>0 &lt;= profit[i] &lt;= 100</code></li>
</ul>

from typing import List


class Solution:
    def __init__(self) -> None:
        self.dp = []
        self.group = []
        self.crimes = []
        self.group_size = -1
        self.min_profit = -1

        self.mod = 10**9 + 7

    def solve(self, idx: int, group: int, profit: int) -> int:
        if idx >= len(self.crimes):
            return 1 if profit >= self.min_profit else 0

        if self.dp[idx][group][profit] != -1:
            return self.dp[idx][group][profit]

        # Aqui vamos contar quantos esquemas são possíveis se o grupo não escolher esse crime.
        total = self.solve(idx + 1, group, profit)

        # Aqui vamos contar quantos são possíveis se o grupo ainda tiver pessoas disponíveis e resolver cometer o crime.
        if (group + self.group[idx]) <= self.group_size:
            total += self.solve(
                idx + 1,
                group + self.group[idx],
                min(self.crimes[idx] + profit, self.min_profit),
            )

        # Salvando e retornando o resultado
        self.dp[idx][group][profit] = total % self.mod
        return self.dp[idx][group][profit]

    def profitableSchemes(
        self, n: int, minProfit: int, group: List[int], profit: List[int]
    ) -> int:
        self.min_profit = minProfit
        self.group_size = n
        self.group = group
        self.crimes = profit

        for _ in range(len(profit) + 1):
            group_count = []
            for _ in range(n + 1):
                group_count.append([-1] * (minProfit + 1))
            self.dp.append(group_count)

        self.solve(0, 0, 0)
        return self.dp[0][0][0]

44817