二八笙歌云幕下
三千世界雪花中
使用dp解本题的关键在于理解 如果今天发现7天前买周票，则到今天的总消费最低这件事，不会改变昨天的最低总消费，也不会改变前天的最低总消费，当然也不改变之前任何一天的最低总消费。换句话说，完全可以当作，如果一周前买了周票，则最后结算的那天才算钱，前面都不算钱！！！。
题目本身是很简单的，理解我刚刚说的那部分。。。这个就是最简单的dp题，不需要任何复杂的状态转换。
即：
\[dp(x) = min\{ dp(x - 1) + costs(0), dp(x - 7) + costs(1), dp(x - 30) + costs(2)\}\]非常简单的公式。。。
代码也是非常简单。
class Solution {
public:
int mincostTickets(vector<int>& days, vector<int>& costs) {
int len = days.size();
int last_day = days[len - 1];
vector<int> dp(last_day + 1, 0);
for (const int &it : days) dp[it] = -1;
for (int i = 1; i <= last_day; i++) {
if (dp[i] == 0)
dp[i] = dp[i - 1];
else {
int a = dp[i - 1] + costs[0];
int b = i - 7 >= 0 ? dp[i - 7] + costs[1] : costs[1];
int c = i - 30 >= 0 ? dp[i - 30] + costs[2] : costs[2];
dp[i] = min({a, b, c});
}
}
return dp[last_day];
}
};
