983. 最低票价 C++

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        // 状态定义： f[i] 表示 i 天及之后 旅行所需的最小花费
        int f[366]{};
        
        // 标注哪些天 出门
        for (int v: days) f[v] = 1;
        
        // 由于状态转移是逆向的 所以倒序 初始状态为 第365天，如果出门了，因为是最后一天所以买一张最便宜的通行证就行了 否则f[365]就是0
        f[365] = f[365] == 1 ? min(costs[0], min(costs[1], costs[2])) : 0;
        
    
        for (int i = 364; i > -1; --i) {
            if (f[i] > 0) {
                int d1 = i+1 < 366 ? costs[0] + f[i+1] : costs[0];
                int d7 = i+7 < 366 ? costs[1] + f[i+7] : costs[1];
                int d30 = i+30 < 366 ? costs[2] + f[i+30] : costs[2];
                // 如果在第i天出门，那么f[i] 要更新，买一天的票的成本加上下一天的最少费用，买七天的票的成本加上之后第8天的最少费用，买30天的票的成本加上第30天之后的最少费用，他们三者取最小值
                f[i] = min(d1, min(d7,d30));
            } else {
                //如果不出门 就是下一天的最小费用
                f[i] = f[i+1];
            }
        }
        return f[0];
    }
};

类似题目：

2140. 解决智力问题