火车旅行最低票价问题--动态规划--Python3

Velika ·

更新时间:2024-09-21

· 540 次阅读

题目

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

火车票有三种不同的销售方式：

一张为期一天的通行证售价为 costs[0] 美元；
一张为期七天的通行证售价为 costs[1] 美元；
一张为期三十天的通行证售价为 costs[2] 美元。

通行证允许数天无限制的旅行。例如，如果我们在第 2 天获得一张为期 7 天的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-cost-for-tickets

火车票有三种不同的销售方式：

一张为期一天的通行证售价为 costs[0] 美元；
一张为期七天的通行证售价为 costs[1] 美元；
一张为期三十天的通行证售价为 costs[2] 美元。

返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-cost-for-tickets

题解

动态规划的转移方程没什么好说的，一眼就能看明白。但是为什么是这个转移方程呢？很多题解都没有提到，需要按照贪心策略去推导转移方程。
第i天不出行，那么第i天可以什么也不干，也可以买任意一种票，但是最优解肯定是什么也不干，延续第i - 1天的花费。
第i天要出行，那么第i天必然要有票。表面上看取决于前几天是不是有7天票，30天票，但是到底取决于哪一天？按照贪心原则，为了让当天的花费平均成本最低，那么7天票最好是就在7天前买的，30天票就是30天买的，还有一种就是当天直接买一张一天票。这三个选择选个最小的值就是推导值，这也是转移方程的得来。
class Solution(object):
def mincostTickets(self, days, costs):
“”"
:type days: List[int]
:type costs: List[int]
:rtype: int
“”"
days_set = set(days)
max_day = days[-1]
dp = [0] * (max_day + 1)
for i in range(1, max_day + 1):
if i not in days_set:
dp[i] = dp[i - 1]
else:
dp_7 = 0 if i - 7 < 0 else dp[i - 7]
dp_30 = 0 if i - 30 < 0 else dp[i - 30]
dp[i] = min(dp[i - 1] + costs[0],
dp_7 + costs[1],
dp_30 + costs[2])