What is the main algorithmic technique used in Profitable Schemes?

The problem primarily uses state transition dynamic programming to efficiently count the number of valid schemes.

How can I optimize space complexity in this problem?

To optimize space, you can reduce the dimensions of the DP table, potentially using only a 2D table or a rolling array approach.

What are the edge cases to consider in Profitable Schemes?

Edge cases include scenarios where no valid schemes can be formed, and ensuring the modulo operation is applied consistently.

What role does the modulo operation play in the solution?

The modulo operation ensures that the result stays within the problem's constraints and avoids overflow due to large numbers.

How does the dynamic programming approach help in solving Profitable Schemes?

Dynamic programming helps by breaking down the problem into manageable subproblems, allowing efficient tracking of group sizes and profits across multiple crime combinations.

#879

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

盈利计划

集团里有 n 名员工，他们可以完成各种各样的工作创造利润。第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。工作的任何至少产生 minProfit 利润的子集称为盈利计划。并且工作的成员总数最多为 n…

数组动态规划

题目描述

集团里有 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 <= 100
0 <= minProfit <= 100
1 <= group.length <= 100
1 <= group[i] <= 100
profit.length == group.length
0 <= profit[i] <= 100

lightbulb

解题思路

方法一：记忆化搜索

我们设计一个函数 $dfs(i, j, k)$ ，表示从第 $i$ 个工作开始，且当前已经选择了 $j$ 个员工，且当前产生的利润为 $k$ ，这种情况下的方案数。那么答案就是 $dfs(0, 0, 0)$ 。

函数 $dfs(i, j, k)$ 的执行过程如下：

如果 $i = n$ ，表示所有工作都已经考虑过了，如果 $k \geq minProfit$ ，则方案数为 $1$ ，否则方案数为 $0$ ；
如果 $i \lt n$ ，我们可以选择不选择第 $i$ 个工作，此时方案数为 $dfs(i + 1, j, k)$ ；如果 $j + group[i] \leq n$ ，我们也可以选择第 $i$ 个工作，此时方案数为 $dfs(i + 1, j + group[i], \min(k + profit[i], minProfit))$ 。这里我们将利润上限限制在 $minProfit$ ，是因为利润超过 $minProfit$ 对我们的答案没有任何影响。

最后返回 $dfs(0, 0, 0)$ 即可。

为了避免重复计算，我们可以使用记忆化搜索的方法，用一个三维数组 $f$ 记录所有的 $dfs(i, j, k)$ 的结果。当我们计算出 $dfs(i, j, k)$ 的值后，我们将其存入 $f[i][j][k]$ 中。调用 $dfs(i, j, k)$ 时，如果 $f[i][j][k]$ 已经被计算过，我们直接返回 $f[i][j][k]$ 即可。

时间复杂度 $O(m \times n \times minProfit)$ ，空间复杂度 $O(m \times n \times minProfit)$ 。其中 $m$ 和 $n$ 分别为工作的数量和员工的数量，而 $minProfit$ 为至少产生的利润。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def profitableSchemes(
        self, n: int, minProfit: int, group: List[int], profit: List[int]
    ) -> int:
        @cache
        def dfs(i: int, j: int, k: int) -> int:
            if i >= len(group):
                return 1 if k == minProfit else 0
            ans = dfs(i + 1, j, k)
            if j + group[i] <= n:
                ans += dfs(i + 1, j + group[i], min(k + profit[i], minProfit))
            return ans % (10**9 + 7)

        return dfs(0, 0, 0)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Assess the candidate's understanding of dynamic programming techniques, especially state transition methods.
question_mark
Evaluate the candidate's ability to handle modulo operations and large numbers in dynamic programming.
question_mark
Check how well the candidate optimizes space complexity while managing a DP table for this type of problem.

warning

常见陷阱

外企场景

error
Forgetting to apply the modulo $10^9 + 7$ when updating the DP table or returning the result.
error
Incorrectly updating the DP table when considering the number of group members for each crime.
error
Not handling edge cases where no valid schemes meet the profit condition.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Increased complexity when adding more crimes and larger group sizes, requiring more sophisticated dynamic programming approaches.
arrow_right_alt
Modifications where the number of crimes can exceed the group size, requiring different combinatorial handling.
arrow_right_alt
Extension to include specific constraints on which crimes can be paired based on external conditions.

help

常见问题

外企场景

继续练习

#877 石子游戏 #873 最长的斐波那契子序列的长度 #871 最低加油次数