983. Minimum Cost For Tickets

佚名 6年前 (2019-04-24) 随笔 1992人围观抢沙发百度已收录

网址：https://leetcode.com/problems/minimum-cost-for-tickets/

参考：https://leetcode.com/problems/minimum-cost-for-tickets/discuss/226659/Two-DP-solutions-with-pictures

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

class Solution
{
public:
    int mincostTickets(vector<int>& days, vector<int>& costs)
    {
        unordered_set<int> travel(begin(days), end(days));
        vector<int> dp(days.back()+1,0);
        for(int i=1; i<days.back()+1; i++)
        {
            if(travel.find(i) == travel.end())
                dp[i] = dp[i-1];
            else
            {
                dp[i] = min(dp[i-1]+costs[0], dp[max(0, i-7)]+costs[1], dp[max(0, i-30)]+costs[2]);
            }
        }
        return dp[days.back()];
    }
};