leetcode

commit 07bc4982f52d8f67211b5cc2fcf25dda972dcf58
parent 6cbe695502f3e87e5ca5970d7d3f0202657b5ad5
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 28 Mar 2023 11:34:10 +0200

Daily Problem

Diffstat:
A
Problems/0983.cpp
 | 
19
+++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 20 insertions(+), 0 deletions(-)
diff --git a/Problems/0983.cpp b/Problems/0983.cpp
@@ -0,0 +1,19 @@
+class Solution {
+  vector<int> pass = {1, 7, 30};
+  unordered_map<int, int> dp;
+
+public:
+  int mincostTickets(vector<int> &days, vector<int> &costs, int start = 0) {
+    if (start >= days.size()) return 0;
+    if (dp.count(start)) return dp[start];
+
+    int res = INT_MAX;
+    for (int k = 0, j = 0; k < pass.size(); k++) {
+      while (j < days.size() && days[j] - days[start] < pass[k]) j++;
+      res = min(res, costs[k] + mincostTickets(days, costs, j));
+    }
+
+    dp[start] = res;
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -366,6 +366,7 @@ for solving problems.
 |  0974  |   Medium   | [Subarray Sums Divisible by K](Problems/0974.cpp)                                                |
 |  0977  |    Easy    | [Squares of a Sorted Array](Problems/0977.cpp)                                                   |
 |  0980  |    Hard    | [Unique Paths III](Problems/0980.cpp)                                                            |
+|  0983  |   Medium   | [Minimum Cost For Tickets](Problems/0983.cpp)                                                    |
 |  0986  |   Medium   | [Interval List Intersections](Problems/0986.cpp)                                                 |
 |  0989  |    Easy    | [Add to Array-Form of Integer](Problems/0989.cpp)                                                |
 |  0990  |   Medium   | [Satisfiability of Equality Equations](Problems/0990.cpp)                                        |