title
集团里有 n 名员工，他们可以完成各种各样的工作创造利润。
第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。
工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。
有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。
示例 1：
输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]
输出：2
解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。
总的来说，有两种计划。
示例 2：
输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
输出：7
解释：至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。
有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。
提示：
1 <= n <= 1000 <= minProfit <= 1001 <= group.length <= 1001 <= group[i] <= 100profit.length == group.length0 <= profit[i] <= 100
solution
记忆化搜索dfs会超时，DP递推就不会超时。 group排序没啥用，但可以用来剪枝，这里没剪枝。
这里的profit和人数看做体积，人数为至多，profit为至少。是个同时有至多、至少的好题目。
可以空间优化少一维。
先dfs，再递推容易想。
class Solution:
def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
MOD = int(1e9 + 7)
d = [(group[i], profit[i]) for i in range(len(group))]
d.sort(reverse=True)
group = [v[0] for v in d]
profit = [v[1] for v in d]
import functools
@functools.lru_cache(None)
def f(i, c, p):
if i == 0:
if c >= 0 and p <= 0:
return 1
return 0
res = 0
# not select
res += f(i - 1, c, p)
# select
if c - group[i - 1] >= 0:
res += f(i - 1, c - group[i - 1], p - profit[i - 1])
res %= MOD
return res
# ans = f(len(group), n, minProfit)
# f.cache_clear()
# return ans
dp = [[0 for _ in range(minProfit + 1)] for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = 1
for i in range(1, len(group) + 1):
for c in range(n, -1, -1):
if c - group[i - 1] >= 0:
for p in range(minProfit, -1, -1):
dp[c][p] += dp[c - group[i - 1]][max(0, p - profit[i - 1])]
dp[c][p] %= MOD
# print(dp)
# assert ans == dp[n][minProfit]
return dp[n][minProfit]