Profitable Schemes Python Solution with Tests

lcpy gen -n 879   # by problem number
lcpy gen -s profitable_schemes   # by problem name

Input: n = 5, minProfit = 3, group = [2,2], profit = [2,3]
Output: 2
Explanation: 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.

Input: n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
Output: 7
Explanation: Every subset of the crimes has total members at most 10 and profit at least 5,
and 7 subsets exist, so all of them are profitable schemes.

class Solution:
    # Time: O(len(group) * n * min_profit)
    # Space: O(n * min_profit)
    def profitable_schemes(
        self, n: int, min_profit: int, group: list[int], profit: list[int]
    ) -> int:
        mod = 1_000_000_007
        dp = [[0] * (min_profit + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        for members, gain in zip(group, profit, strict=True):
            for used in range(n, members - 1, -1):
                for earned in range(min_profit, -1, -1):
                    new_earned = min(min_profit, earned + gain)
                    dp[used][new_earned] = (dp[used][new_earned] + dp[used - members][earned]) % mod
        return sum(dp[used][min_profit] for used in range(n + 1)) % mod