leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0983.cpp (576B)

      1 class Solution {
      2     vector<int> pass = {1, 7, 30};
      3     unordered_map<int, int> dp;
      4 
      5   public:
      6     int mincostTickets(vector<int> &days, vector<int> &costs, int start = 0) {
      7         if (start >= days.size()) return 0;
      8         if (dp.count(start)) return dp[start];
      9 
     10         int res = INT_MAX;
     11         for (int k = 0, j = 0; k < pass.size(); k++) {
     12             while (j < days.size() && days[j] - days[start] < pass[k])
     13                 j++;
     14             res = min(res, costs[k] + mincostTickets(days, costs, j));
     15         }
     16 
     17         dp[start] = res;
     18         return res;
     19     }
     20 };