Leetcode 983

题目要求

给定days ( days[i]∈ [1, 365] ) 数组和costs数组，costs[0]表示覆盖Days中的1天所需的cost，[1]连续7天，[2]连续30天。求能覆盖完days数组中所有元素所需的最小total cost

核心算法和原理

• 最优子结构：对整个问题的最优覆盖可以分为多个最优子覆盖的和

• dp数组含义：dp[i] 表示「 在覆盖days[i - 1]及之前所有日期的情况下最小cost 」

• 状态转移方程 + 边界情况：
• i ≥ 1

代码

class Solution {
public:
    vector<int> memo;
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        std::ios_base::sync_with_stdio(false);
        std::cin.tie(nullptr);
        memo = vector<int> (days.size() + 1, -1);
        memo[0] = 0;
        // memo[i] ~ days[i - 1]
        for (int i = 1; i <= days.size(); i++) {
            int cost1, cost7, cost30, idx;
            cost1 = costs[0] + memo[i-1];

            idx = i - 2;
            while(idx >= 0 && days[i-1] - days[idx] < 7) {
                idx--;
            }
            cost7 = costs[1] + memo[idx + 1];

            idx = i - 2;
            while(idx >= 0 && days[i-1] - days[idx] < 30) {
                idx--;
            }
            cost30 = costs[2] + memo[idx + 1];
            memo[i] = min(cost1, min(cost7, cost30));
        }
        return memo[days.size()];
    }

};