|
41 | 41 | You are not allowed to buy more items than you want, even if that would lower the overall price. |
42 | 42 | */ |
43 | 43 | publicclass_638 { |
44 | | -/**reference: https://leetcode.com/articles/shopping-offers/#approach-1-using-recursion-accepted*/ |
45 | | -publicintshoppingOffers(List<Integer>price,List<List<Integer>>special,List<Integer>needs) { |
46 | | -returnshopping(price,special,needs,0); |
47 | | - } |
48 | | - |
49 | | -publicintshopping(List<Integer>price,List<List<Integer>>special,List<Integer>needs,inti) { |
50 | | -if (i ==special.size()) { |
51 | | -returndot(needs,price); |
| 44 | +publicstaticclassSolution1 { |
| 45 | +/** |
| 46 | + * reference: https://leetcode.com/articles/shopping-offers/#approach-1-using-recursion-accepted |
| 47 | + */ |
| 48 | +publicintshoppingOffers(List<Integer>price,List<List<Integer>>special,List<Integer>needs) { |
| 49 | +returnshopping(price,special,needs,0); |
52 | 50 | } |
53 | | -ArrayList<Integer>clone =newArrayList(needs); |
54 | | -intj =0; |
55 | | -for (j =0;j <special.get(i).size() -1;j++) { |
56 | | -intdiff =clone.get(j) -special.get(i).get(j); |
57 | | -if (diff <0) { |
58 | | -break; |
| 51 | + |
| 52 | +publicintshopping(List<Integer>price,List<List<Integer>>special,List<Integer>needs,inti) { |
| 53 | +if (i ==special.size()) { |
| 54 | +returndot(needs,price); |
| 55 | + } |
| 56 | +ArrayList<Integer>clone =newArrayList(needs); |
| 57 | +intj =0; |
| 58 | +for (j =0;j <special.get(i).size() -1;j++) { |
| 59 | +intdiff =clone.get(j) -special.get(i).get(j); |
| 60 | +if (diff <0) { |
| 61 | +break; |
| 62 | + } |
| 63 | +clone.set(j,diff); |
| 64 | + } |
| 65 | +if (j ==special.get(i).size() -1) { |
| 66 | +returnMath.min(special.get(i).get(j) +shopping(price,special,clone,i),shopping(price,special,needs,i +1)); |
| 67 | + }else { |
| 68 | +returnshopping(price,special,needs,i +1); |
59 | 69 | } |
60 | | -clone.set(j,diff); |
61 | | - } |
62 | | -if (j ==special.get(i).size() -1) { |
63 | | -returnMath.min(special.get(i).get(j) +shopping(price,special,clone,i),shopping(price,special,needs,i +1)); |
64 | | - }else { |
65 | | -returnshopping(price,special,needs,i +1); |
66 | 70 | } |
67 | | - } |
68 | 71 |
|
69 | | -publicintdot(List<Integer>a,List<Integer>b) { |
70 | | -intsum =0; |
71 | | -for (inti =0;i <a.size();i++) { |
72 | | -sum +=a.get(i) *b.get(i); |
| 72 | +publicintdot(List<Integer>a,List<Integer>b) { |
| 73 | +intsum =0; |
| 74 | +for (inti =0;i <a.size();i++) { |
| 75 | +sum +=a.get(i) *b.get(i); |
| 76 | + } |
| 77 | +returnsum; |
73 | 78 | } |
74 | | -returnsum; |
75 | 79 | } |
76 | 80 | } |