983. Minimum Cost For Tickets

發表於 | 分類於

problem

solution

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
class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        
        //      1   4   6   7   8   20
        //1     2   4   6   8   10  12
        //7     2   4   6   7   9   11
        //30    2   4   6   7   9   11
        
        
        int n = days.size(), m = costs.size();
        vector<int> dp(n+1,0);
        // init
        dp[0] = 0;
        for(int i=1;i<n+1;++i){
            // 確定第 i 天花最少錢
            
            // one day
            dp[i] = dp[i-1] + costs[0];
            for(int j=1;j<=i;++j){
                
                if( days[i-1] - days[j-1] < 7) dp[i] = min(dp[i], dp[j-1] + costs[1]);
                if( days[i-1] - days[j-1] < 30) dp[i] = min(dp[i], dp[j-1] + costs[2]);
            }
        }
        
        return dp.back();
        
    }
};

analysis

  • time complexity O(nm)
  • space complexity O(n)