HardNo. 0879
Profitable Schemes — LeetCode 879 Python Solution
- Pattern
- Dynamic Programming
- Topics
- Array, Dynamic Programming
- Reading time
- 3 min
- Source
- leetcode.com
The problem
There is a group of n members, and a list of various crimes they could commit. The ith crime generates a profit[i] and requires group[i] members to participate in it.
Example
- 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.
Python solution
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)Complexity
- Time
- O(m × n × minProfit), and th e space complexity is O(m × n × minProfit)
- Space · auxiliary
- O(m × n × minProfit)
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 879. Profitable Schemes is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0877 | Stone Game | Medium |
| 0871 | Minimum Number of Refueling Stops | Hard |
| 0045 | Jump Game II | Medium |
| 0053 | Maximum Subarray | Medium |
| 0055 | Jump Game | Medium |
| 0063 | Unique Paths II | Medium |
Frequently asked questions
- How hard is LeetCode 879. Profitable Schemes?
LeetCode 879. Profitable Schemes is rated Hard on LeetCode.
- What is the time complexity of LeetCode 879. Profitable Schemes?
The Python solution on this page runs in O(m × n × minProfit), and th e space complexity is O(m × n × minProfit).
- What is the space complexity of LeetCode 879. Profitable Schemes?
The Python solution on this page uses O(m × n × minProfit) auxiliary space.
- What topics does LeetCode 879. Profitable Schemes cover?
LeetCode 879. Profitable Schemes is tagged Array and Dynamic Programming on LeetCode.