leetcode每日一题day21(24.10.1)——最低票价
看到题目，最低消费又有各种的方案，与结合往期每日一题很就没出动态规划，就感觉这题很像动态规划。
思路:对于第X天，买票有三种方案，即从，X-1天买一天的票，X-7买7天的票，X-30买三十天的票，这已经很有，走楼梯，斐波那契的味道了，需要注意的是，总天数不到30天也是能买30天的票的这也比较合理，设定一个含义为：第1到第i天最少的花费为dp[i]，据此写出了如下代码。
int mincostTickets(vector<int>& days, vector<int>& costs) {int dp[366] = {0}, last_day = days[days.size() - 1], temp;for (int day = 1, index = 0; day <= last_day; day++) {dp[day] = dp[day - 1] + costs[0];temp = day - 7 < 0 ? 0 : day - 7;dp[day] = min(dp[day], costs[1] + dp[temp]);temp = day - 30 < 0 ? 0 : day - 30;dp[day] = min(dp[day], costs[2] + dp[temp]);index++;}return dp[last_day];}如上代码 对于样例
输入：days = [1,4,6,7,8,20], costs = [2,7,15] 输出：11 得到的dp数组为：2 4 6 7 7 7 7 9 11 13 14 14 14 14 15 15 15 15 15 15
很明显是不对的，所有与走楼梯问题有所不同，至于哪里不同呢，可以观察到，对于第19天竟然也需要15元的钱，来源很明显是从0买三十天的票而来，之所以会这样是考虑了9-19天也买票，但事实上，第八天过后是不需要买票的，只需要第20天买一张单日票即可。
对于上述问题，我们只需要，更改dp数组更新机制，只有在有旅游安排的日子，更改dp，其他时刻沿用，当日之前的有旅游安排的日子的dp值即可，
换成偏编程的表达方式就是，对于有旅游安排的日子采用最初的方案，对于没有旅游安排的日子，由于其不需要买票，则继续沿用前一天的dp值即可。将代码更新为如下情况
int mincostTickets(vector<int>& days, vector<int>& costs) {int dp[366] = {0}, last_day = days[days.size() - 1], temp;for (int day = 1, index = 0; day <= last_day; day++) {if (day < days[index]) {dp[day] = dp[day - 1];continue;}dp[day] = dp[day - 1] + costs[0];temp = day - 7 < 0 ? 0 : day - 7;dp[day] = min(dp[day], costs[1] + dp[temp]);temp = day - 30 < 0 ? 0 : day - 30;dp[day] = min(dp[day], costs[2] + dp[temp]);index++;}for (int day = 1; day <= last_day; day++) {cout << dp[day] << " ";}return dp[last_day];}此时得到的dp数组为：2 2 2 4 4 6 7 9 9 9 9 9 9 9 9 9 9 9 9 11