# 0983. Minimum Cost For Tickets
###### tags: `Leetcode` `Medium` `Dynamic Programming` `Greedy`
Link: https://leetcode.com/problems/minimum-cost-for-tickets/
## 思路
假设第```i```天当日我们不需要乘车，那么前```i```天乘车的花费```dp[i]```就完全等同于```dp[i-1]```。

假设第```i```天当日我们需要乘车，那么```dp[i]```只需要考虑三种前驱状态：1. 在第```i-1```天买张日票，2. 在第```i-7```天买张周票，3. 在第```i-30```天买张月票，所以```dp[i]```就是在```dp[i-1]+cost[0]```, ```dp[i-7]+cost[1]```, ```dp[i-30]+cost[2]```中取最小值就可。

greedy的思想体现在如果用周票/月票划算那么越早用越好 所以我们才会去尝试用第```i```天当作票的最后一天 (这个思想也用在了[2209. Minimum White Tiles After Covering With Carpets](https://hackmd.io/UEAOe9NtRSSb7fQkrmefhw)上面)
## Code

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        Arrays.sort(days);
        int n = days.length;
        int max = days[n-1];
        int idx = 0;
        
        int[] dp = new int[max+1];
        for(int i=1; i<=max; i++){
            if(idx<n && i==days[idx]){
                int a = dp[Math.max(0, i-1)]+costs[0];
                int b = dp[Math.max(0, i-7)]+costs[1];
                int c = dp[Math.max(0, i-30)]+costs[2];
                dp[i] = Math.min(Math.min(a,b),c);
                idx++;
            }
            else{
                dp[i] = dp[i-1];
            }
        }
        return dp[max];
    }
}