leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

minimum-cost-for-tickets.dart (1953B)

      1 //Return the minimum cost of traveling on a train 
      2 //for n days where n are the values in the days list.
      3 //The ticket prices vary depending on the length they are good for.
      4 //There is a week pass, month pass, and day pass each of which
      5 //makes it so you can ride on the train for a given number of days
      6 //in a row. To solve this I used recursion along with memoization
      7 //to find the minimum cost from each day working my way backwards until finding
      8 //the minimum cost from the first day.
      9 //The time compexity of this code is O(n) where n is the number of nodes in the list.
     10 //Time: 296ms Beats: 62.50%
     11 //Memory: 145.1MB Beats: 25%
     12 class Solution {
     13   Map<int, int> memo = {};
     14   int mincostTickets(List<int> days_, List<int> costs) {
     15       if(memo[days_.length] != null){
     16           int return_int = (memo[days_.length] ?? 0);
     17           return return_int;
     18       }
     19 
     20       List<int> days = List.from(days_);
     21       if(days.length == 0){
     22           return 0;
     23       }
     24       int date = days[0];
     25       days.removeAt(0);
     26       int one_day = mincostTickets(days, costs);
     27 
     28       for(int i = 0 ; i < days.length ; ++i){
     29           if(days[i] < date + 7){
     30               days.removeAt(0);
     31               --i;
     32           }
     33           else{
     34               break;
     35           }
     36       }
     37       int week = mincostTickets(days , costs);
     38 
     39       for(int i = 0 ; i < days.length ; ++i){
     40           if(days[i] < date + 30){
     41               days.removeAt(0);
     42               --i;
     43           }
     44           else{
     45               break;
     46           }
     47       }
     48       int month = mincostTickets(days, costs);
     49       month += costs[2];
     50       week += costs[1];
     51       one_day += costs[0];
     52       int return_val = 0;
     53       if(month <= one_day && month <= week){
     54           return_val = month;
     55       }
     56       else if(one_day <= month && one_day <= week){
     57           return_val = one_day;
     58       }
     59       else{
     60           return_val = week;
     61       }
     62 
     63       memo[days_.length] = return_val;
     64       return return_val;
     65 
     66   }
     67 }