Posted on 2023-04-21 19:29
Uriel 閱讀(40)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
閑來無事重切Leet Code
DP，方法參考Discussion->https://leetcode.com/problems/profitable-schemes/solutions/3439511
1 #879
2 #Runtime: 2252 ms (Beats 62.50%)
3 #Memory: 42.7 MB (Beats 37.50%)
4
5 class Solution(object):
6 def profitableSchemes(self, n, minProfit, group, profit):
7 """
8 :type n: int
9 :type minProfit: int
10 :type group: List[int]
11 :type profit: List[int]
12 :rtype: int
13 """
14 MOD = 10**9 + 7
15 m = len(group)
16 dp = [[[0] * (minProfit + 1) for _ in range(n + 1)] for _ in range(m + 1)]
17 for j in range(n + 1):
18 dp[0][j][0] = 1
19 for i in range(1, m + 1):
20 for j in range(n + 1):
21 for k in range(minProfit + 1):
22 dp[i][j][k]=dp[i - 1][j][k]
23 if j >= group[i - 1]:
24 dp[i][j][k] += dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])]
25 dp[i][j][k] %= MOD
26 return dp[m][n][minProfit]