forked from fishercoder1534/Leetcode
-
Notifications
You must be signed in to change notification settings - Fork 1
/
_638.java
43 lines (39 loc) · 1.47 KB
/
_638.java
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
package com.fishercoder.solutions;
import java.util.ArrayList;
import java.util.List;
public class _638 {
public static class Solution1 {
/**
* reference: https://leetcode.com/articles/shopping-offers/#approach-1-using-recursion-accepted
*/
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
return shopping(price, special, needs, 0);
}
public int shopping(List<Integer> price, List<List<Integer>> special, List<Integer> needs, int i) {
if (i == special.size()) {
return dot(needs, price);
}
ArrayList<Integer> clone = new ArrayList(needs);
int j = 0;
for (; j < special.get(i).size() - 1; j++) {
int diff = clone.get(j) - special.get(i).get(j);
if (diff < 0) {
break;
}
clone.set(j, diff);
}
if (j == special.get(i).size() - 1) {
return Math.min(special.get(i).get(j) + shopping(price, special, clone, i), shopping(price, special, needs, i + 1));
} else {
return shopping(price, special, needs, i + 1);
}
}
public int dot(List<Integer> a, List<Integer> b) {
int sum = 0;
for (int i = 0; i < a.size(); i++) {
sum += a.get(i) * b.get(i);
}
return sum;
}
}
}