最低票价

Leetcode题目链接

描述

详见中文题目链接。

解答

class Solution {
private:
    array<int, 3> durations{1, 7, 30};

    int calculate(const vector<int>& days, const vector<int>& costs, int start, vector<int>& dp) {
        if (start == days.size()) {
            return 0;
        }

        if (dp[start] != numeric_limits<int>::max()) {
            return dp[start];
        }

        int res = numeric_limits<int>::max();
        for (int option = 0, j = start; option < 3; option++) {
            while (j < days.size() && days[start] + durations[option] > days[j]) {
                j++;
            }
            res = min(res, costs[option] + calculate(days, costs, j, dp));
        }

        dp[start] = res;

        return res;
    }

public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        vector<int> dp(days.size(), numeric_limits<int>::max());
        return calculate(days, costs, 0, dp);
    }
};