#LeetCode刷题笔记# 983 最低票价 (python版）

题目来源：力扣(LeetCode)

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

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

通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张为期 7 天的通行证，
那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。
返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费。

示例 1：
输入：days = [1,4,6,7,8,20], costs = [2,7,15]
输出：11
解释：
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生效。
在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, …, 9 天生效。
在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。
你总共花了 $11，并完成了你计划的每一天旅行。

示例 2：
输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
输出：17
解释：
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
在第 1 天，你花了 costs[2] = $15 买了一张为期 30 天的通行证，它将在第 1, 2, …, 30 天生效。
在第 31 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 31 天生效。
你总共花了 $17，并完成了你计划的每一天旅行。

提示：
1 <= days.length <= 365
1 <= days[i] <= 365
days 按顺序严格递增
costs.length == 3
1 <= costs[i] <= 1000

拿到这题，没思路。 看完官方解答，（代码）不懂…，不熟悉python的一些用法。emmmmm
怪自己太菜。手码一下，以理清思路。

---

解法1的思路：

由题目可知，$days$的取值范围为[1,365]，长度也在[1,365]内，也就是说我们只用考虑365天内的。
设$dp[i]$表示第$i$天到365天我们最少需要花费的钱。因此$dp[1]$为我们要求的结果。
在这一年中，并不是每一天都要买票，按照贪心的思想，越晚买票越好，因此只有在旅游日，我们才有可能会去买票。
假设我们已经求得了$dp[i]$，若第$i-1$天不是旅游日，则不需要买票，因此有：
$$dp[i-1]=dp[i]$$
若第$i-1$天需要买票，我们可以选择第$i-1$天买1天的通行证，那么此时的花费为$cost[0]+dp[i]$，但这不是唯一的方式，我们同样可以选择买7天的通行证。但是若第$i-1$天买了7天的通行证，那我们在第$i$至第$i+5$天内都不需要买票了，因此此时相对的最小花费为$cost[1]+dp[i+6]$。同理若在第$i-1$天买了30天的通行证，则此时相对的最小花费为$cost[2]+dp[i+29]$，我们应该在这三种方案中选择一个花费最小的，因此有：
$$dp[i-1]=min(cost[0]+dp[i],cost[1]+dp[i+6],cost[2]+dp[i+29])$$
设一个数组$last$，$last[j]$表示第$j$张通行证可游玩$last[j]$天。即，$last[0]=1$，$last[1]=7$，$last[2]=30$

整理下可得到最终的递推表达式:
d p [ i ] = { d p [ i + 1 ] ， 若 第 i 天 不 是 旅 游 日 m i n ( c o s t [ j ] + d p [ i + l a s t [ j ] ] ) ， 若 第 i 天 是 旅 游 日 ， j = 1 , 2 , 3 dp[i] = \left\{

$$\begin{array}{ll} dp[i+1]，&若第i天不是旅游日\\ \mathrm{min}(cost[j]+dp[i+last[j]])，&若第i天是旅游日，j = 1,2,3 \end{array}$$ \right. dp[i]={dp[i+1]，min(cost[j]+dp[i+last[j]])，​若第i天不是旅游日若第i天是旅游日，j=1,2,3​

以示例1为例，days = [1,4,6,7,8,20], costs = [2,7,15]
当$i>20$时，$dp[i]=0$
所以：$dp[20]=min(cost[0]+dp[21],cost[1]+dp[27],cost[2]+dp[50])=2$
第9-19天都不是旅游日，因此：
当$8<i<20$时，dp[i] = dp[20] = 2
当$i=8$时，需要买票了
$dp[8]=min(cost[0]+dp[9],cost[1]+dp[15],cost[2]+dp[38])=4$
依次类推有：
$dp[7]=min(cost[0]+dp[8],cost[1]+dp[14],cost[2]+dp[37])=6$
$dp[6]=min(cost[0]+dp[7],cost[1]+dp[13],cost[2]+dp[36])=8$
$dp[5]=dp[6]=8$
$dp[4]=min(cost[0]+dp[5],cost[1]+dp[11],cost[2]+dp[34])=9$
$dp[2]=dp[3]=dp[4]=9$
$dp[1]=min(cost[0]+dp[2],cost[1]+dp[8],cost[2]+dp[31])=11$

接下来看下代码实现
以下是按官方解答默写的Python3代码

# 解法1
class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        last = [1,7,30]

        @lru_cache(None)
        def dp(i):
            if i > 365:
                return 0
            elif i in days:
                return min(c+dp(i+l) for c, l in zip(costs, last))
            else:
                return dp(i+1)
        return dp(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

代码说明

• 这里采用了递归。
• @lru_cache(None) 是缓存装饰器。

lru_cache(maxsize=128, typed=False)

• maxsize表示最大缓存数。若maxsize=None,则禁用LRU功能，并且缓存可以无限制增长；当maxsize=$2^m$时，LRU功能执行得最好；
• 若typed=True, 则不同类型的函数参数将单独缓存。例如，f(3)和f(3.0)将被视为具有不同结果的不同调用；
• 缓存是有内存存储空间限制的；

使用这个装饰器后，可以保存函数的调用结果，@lru_cache(None) 装饰器适合于耗时的函数。
ps： LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法

• zip() 函数用于将可迭代的对象作为参数，将对象中对应的元素打包成一个个元组，然后返回由这些元组组成的列表。

可以很容易地将其改为非递归形式：

# 版本1， 使用了长度为396的数组dp，第一个元素没有意义，
# 后面多余的30个元素只是为了循环时不超出索引限制
# 该版本简单好实现，但是运行较慢，浪费的空间也比较多
class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        last = [1, 7, 30]
        dp = [0 for _ in range(396)]
        for i in reversed(range(366)):
            if i not in days:
                dp[i] = dp[i+1]
            else:
                dp[i] = min(c+dp[i+l] for c, l in zip(costs, last))
        return dp[1]
1
2
3
4
5
6
7
8
9
10
11
12
13

# 版本2，其实从days[-1]天开始计算即可
class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        last = [1, 7, 30]
        dp = [0 for _ in range(366)]
        for i in reversed(range(1,days[-1]+1)):
            if i not in days:
                dp[i] = dp[i+1]
            else:
                dp[i] = min(c+dp[(i+l)%365] for c, l in zip(costs, last))
        return dp[1]
1
2
3
4
5
6
7
8
9
10
11

也可以将dp倒过来存储结果，此时dp[days[-1]]为最终答案。

#版本3
class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dp = [0 for _ in range(366)]
        for i in range(1,days[-1]+1):   # days[-1]天之后的就不用再计算了
            if i not in days:
                dp[i] = dp[i-1]
            else:
                dp[i] = min(costs[0]+dp[i-1],costs[1]+dp[i-7],costs[2]+dp[i-30])
                
        return dp[days[-1]]
1
2
3
4
5
6
7
8
9
10
11

---

解法2的思路：

在解法1中，需要计算不旅行日子到年末的最小花费，$dp[i]=d[i+1]=dp[i+2]=\dots$这些计算其实都是不需要的。可对其进行改进。
设$dp[i]$ 表示第$days[i]$天到最后一个旅行日$days[-1]$所需的最小花费。
假设$j_1$表示满足$days[j_1]>=days[i]+1$的最小下标，$j_2$表示满足$days[j_2]>=days[i]+7$，$j_3$表示满足$days[j_3]>=days[i]+30$。
例如对于，$days=[1,4,6,7,8,20,40],costs=[2,7,15]$
假设$i=2$，$days[i]=days[2]=6$，那么$j_1=3,j_2=5,j_3=6$。
那么由解法1很容易得到：
$$dp[i]=min(cost[0]+dp[j_1],cost[1]+dp[j_2],cost[2]+dp[j_3])$$
该解法中返回的值应为dp[0]。
代码如下：

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        N = len(days)
        last = [1, 7 ,30]

        @lru_cache(None)
        def dp(i):
            if i == N:
                return 0
            
            res = float('inf')     # 初始化结果为无穷大
            for c, l in zip(costs, last):
                j = i
                while j < N and days[j] < days[i] + l:  # 找j1, j2, j3
                    j += 1
                res = min(res, c+dp(j))    # 递归
            return res
        return dp(0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

也可将以上代码改为非递归形式：

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        N = len(days)
        last = [1, 7, 30]
        dp = [0 for _ in range(N)]
        
        for i in reversed(range(N)):
            res = float('inf')
            if i == N-1:
                dp[i] = min(costs)  # 有个测例给的costs居然不是严格递增的- -
            else:
                j = i
                for c, l in zip(costs, last):
                    while j < N and days[j] < days[i] + l:
                        j = j + 1
                    if j < N:
                        res = min(res,c+dp[j])
                    else:
                        res = min(res,c)  # j可能越界
                    j = i
                dp[i] = res
        return dp[0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

还有其他解法，以后再说吧（捂脸T^T）