最低票价

解题思路

整体思路，
使用dp表，记录当前天数，需要花费的最小价格。
更新规则：
dp[i] = dp[i-1] 当当前天数不需要出去旅游时，则直接使用前一天的花费，也就是当天不用增加花费。
dp[i] = min({dp[max(0, i-1)]+costs[0], dp[max(0,i-7)]+costs[1], dp[max(0, i-30)]+costs[2]}) 表示今天的花费与三种情况有关，选择花费最少的就是当前的解。根据题意，如果使用了2元，则与前一天的花费有关，使用7元则与7天前有关。。
方法注意点：
牢记dp中每一个值已经是最低花费了。
CPP中，多个值得min({。。})使用{}

代码

cpp

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int dp[366];
        dp[0] = 0;
        int idx_day = 0;
        int n =days[days.size()-1];
        for(int i =1; i<=n ;i++){
            if(i != days[idx_day]){
                dp[i] = dp[i-1];
            }else{
                dp[i] = min({dp[max(0, i-1)]+costs[0], dp[max(0,i-7)]+costs[1], dp[max(0, i-30)]+costs[2]});
                idx_day++;
            }
        }
        return dp[n];
        
    }
};