leetcode-java/src/ProfitableSchemes879.java at master · fluency03/leetcode-java · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
/**
 * There are G people in a gang, and a list of various crimes they could commit.
 *
 * The i-th crime generates a profit[i] and requires group[i] gang members to
 * participate.
 *
 * If a gang member participates in one crime, that member can't participate in
 * another crime.
 *
 * Let's call a profitable scheme any subset of these crimes that generates at
 * least P profit, and the total number of gang members participating in that
 * subset of crimes is at most G.
 *
 * How many schemes can be chosen? Since the answer may be very large, return
 * ∂it modulo 10^9 + 7.
 *
 * Example 1:
 * Input: G = 5, P = 3, group = [2,2], profit = [2,3]
 * Output: 2
 * Explanation:
 * To make a profit of at least 3, the gang could either commit crimes 0 and 1,
 * or just crime 1.
 * In total, there are 2 schemes.
 *
 * Example 2:
 * Input: G = 10, P = 5, group = [2,3,5], profit = [6,7,8]
 * Output: 7
 * Explanation:
 * To make a profit of at least 5, the gang could commit any crimes, as long
 * as they commit one.
 *
 * There are 7 possible schemes: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2).
 *
 * Note:
 * 1 <= G <= 100
 * 0 <= P <= 100
 * 1 <= group[i] <= 100
 * 0 <= profit[i] <= 100
 * 1 <= group.length = profit.length <= 100
 */

publicclassProfitableSchemes879 {

publicintprofitableSchemes(intG, intP, int[] group, int[] profit) {
intK = group.length;
int[][][] dp = newint[K + 1][P + 1][G + 1];
dp[0][0][0] = 1;
intmod = (int)1e9 + 7;
for (intk=1; k<=K; k++) {
intpk = profit[k-1];
intgk = group[k-1];
for (inti=0; i<=P; i++) {
for (intj=0; j<=G; j++) {
dp[k][i][j] = (dp[k-1][i][j] + (j < gk ? 0 : dp[k-1][Math.max(0, i-pk)][j - gk])) % mod;
 }
 }
 }

intres = 0;
for (inta: dp[K][P]) {
res = (res + a) % mod;
 }
returnres;
 }


publicintprofitableSchemes2(intG, intP, int[] group, int[] profit) {
intK = group.length;
int[][] dp = newint[P + 1][G + 1];
dp[0][0] = 1;
intmod = (int)1e9 + 7;
for (intk=1; k<=K; k++) {
intpk = profit[k-1];
intgk = group[k-1];

int[][] tmp = newint[P + 1][G + 1];
for (inti=0; i<=P; i++) {
for (intj=0; j<=G; j++) {
tmp[i][j] = dp[i][j];
 }
 }

for (inti=0; i<=P; i++) {
for (intj=0; j<=G; j++) {
dp[i][j] = (tmp[i][j] + (j < gk ? 0 : tmp[Math.max(0, i-pk)][j - gk])) % mod;
 }
 }
 }

intres = 0;
for (inta: dp[P]) {
res = (res + a) % mod;
 }
returnres;
 }


/**
 * https://leetcode.com/problems/profitable-schemes/solution/
 */
publicintprofitableSchemes3(intG, intP, int[] group, int[] profit) {
intMOD = 1_000_000_007;
intN = group.length;
long[][][] dp = newlong[2][P+1][G+1];
dp[0][0][0] = 1;

for (inti = 0; i < N; ++i) {
intp0 = profit[i]; // the current crime profit
intg0 = group[i]; // the current crime group size

long[][] cur = dp[i % 2];
long[][] cur2 = dp[(i + 1) % 2];

// Deep copy cur into cur2
for (intjp = 0; jp <= P; ++jp)
for (intjg = 0; jg <= G; ++jg)
cur2[jp][jg] = cur[jp][jg];

for (intp1 = 0; p1 <= P; ++p1) { // p1 : the current profit
// p2 : the new profit after committing this crime
intp2 = Math.min(p1 + p0, P);
for (intg1 = 0; g1 <= G - g0; ++g1) { // g1 : the current group size
// g2 : the new group size after committing this crime
intg2 = g1 + g0;
cur2[p2][g2] += cur[p1][g1];
cur2[p2][g2] %= MOD;
 }
 }
 }

// Sum all schemes with profit P and group size 0 <= g <= G.
longans = 0;
for (longx: dp[N%2][P])
ans += x;

return (int) (ans % MOD);
 }


/**
 * https://leetcode.com/problems/profitable-schemes/discuss/154617/C++JavaPython-DP
 */
publicintprofitableSchemes4(intG, intP, int[] group, int[] profit) {
int[][] dp = newint[P + 1][G + 1];
dp[0][0] = 1;
intres = 0, mod = (int)1e9 + 7;
for (intk = 0; k < group.length; k++) {
intg = group[k], p = profit[k];
for (inti = P; i >= 0; i--)
for (intj = G - g; j >= 0; j--)
dp[Math.min(i + p, P)][j + g] = (dp[Math.min(i + p, P)][j + g] + dp[i][j]) % mod;
 }
for (intx : dp[P]) res = (res + x) % mod;
returnres;
 }


/**
 * https://www.youtube.com/watch?v=MjOIR61txFc
 */
publicintprofitableSchemes5(intG, intP, int[] group, int[] profit) {
intK = group.length;
int[][] dp = newint[P + 1][G + 1];
dp[0][0] = 1;
intmod = (int)1e9 + 7;
for (intk=1; k<=K; k++) {
intpk = profit[k-1];
intgk = group[k-1];
for (inti=P; i>=0; i--) {
intip = Math.min(P, i + pk);
for (intj=G-gk; j>=0; j--) {
dp[ip][j+gk] = (dp[ip][j+gk] + dp[i][j]) % mod;
 }
 }
 }

intres = 0;
for (inta: dp[P]) {
res = (res + a) % mod;
 }
returnres;
 }


}