问题描述
在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为days的数组给出。每一项是一个从 1 到 365 的整数。
火车票有三种不同的销售方式：
1.一张为期一天的通行证售价为 costs[0] 美元
2.一张为期七天的通行证售价为 costs[1] 美元
3.一张为期三十天的通行证售价为 costs[2] 美元
通行证允许数天无限制的旅行。例如，如果我们在第2天获得一张为期7天的通行证，那么我们可以连着旅行7天：第2天、第3天、第4天、第5天、第6天、第7天和第8天。
返回你想要完成在给定的列表days中列出的每一天的旅行所需要的最低消费。
解决方案
本题是一道较为清晰思路的动态规划题，通过查看力扣解题情况，发现不管使用什么语言，大多都是顺序推出的，所以这里讲一下逆序推出的过程。
正序逆序的区别主要是一个向前累计，一个向后累计，最后得到两边的数就是需要的结果。
梳理一下本题思路：三种票价，分别对应三种天数，我们以从最后一天推导为例，在我们要旅行的最后一天，三种价格的票都可以供我们购买。但择其最优解，很显然就一天，所以买一天的票。此时票价累计便为当前最后一天的票的价格。然后将这种累计存入一个含有要旅行的最后一天天数个元素的列表中，并将其位置与天数位置对应。如果前一天不旅行，这种累计就在列表中向前提一位。
就这样反向遍历，直到遇到下一次要旅行的天数，仍然有三种购票情况：
1.只买一天，后边不管，票价为cost[1]
2.买七天，管后边的七天，后边7天累计置为0
3.买三十天，管后边的30天，后边30天累计置为0
然后根据本次购票与对应情况所产生的累计进行相加，得到本次买票后产生的三种累计情况，用min()函数择其最小，就是当前天数的累计。直到循环到第一个要旅行的天数。产生的累计就是我们需要求得答案，也就是最低票价。
Python代码：
def mincostTickets(days,costs): all_days = days[-1] dp = [0]*(all_days+31)
for i in range(all_days,-1,-1): if i in days: dp[i] = min(dp[i + 1] + costs[0], dp[i + 7] + costs[1], dp[i + 30] + costs[2])
else: dp[i] = dp[i + 1] return dp[0] |
结语
动态规划的一些题目往往不是只有一种最优解，在思考正向规划的同时，考虑一下反向规划，这样可能会从中发现更加准确且高效的解题思路。当然，反向推理时要注意一些边界的细节，否则可能会造成一些小错误。
