LeetCode 983 最低票价
本题属于典型的动态规划题目,而且还有不止一种做法,又能与贪心算法有所联系,算是一道比较优秀的题目。
题目描述
原题链接如下: LeetCode 983 最低票价
题目大意
火车票实行多种不同的通行证方案,购买一个通行证后,在方案规定的天数内可随意乘车,无需再缴费。例如:如果我们在第 2 天获得一张为期 7 天的通行证,那么我们可以连着旅行 7 天:第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。 同时,我们一年内可能在不同的日子都要进行铁路旅行,那么就可以使用多种不同的通行证购买方案,但是根据其价格和时长总会有个花费最少的方案,本题就是要求出这个最少花费。
输入与输出
在接下来的一年(记为 365 天)里,你要旅行的日子储存再一个名为 days 的数组里,数组每一项是一个从 1 到 365 的整数。 火车票有三种价格,记录在长度为 3 的 costs 数组种,数组元素对应不同的通行证时长,分别为:1 天、7 天和 30 天。
示例输入为:
|
|
days 按顺序严格递增,且不会重复
示例输出为:
|
|
解题思路
本题明显可以采用动态规划方法求解,而且题目子问题也容易表达,但是仍然会有两种不同的规划方案供选择。
解法一
直观地定义状态 dp(i) 表示 1 到 i 天的已经支出的车票总花费,最后问题答案就是最大日期对应的 dp(max)。 当天需要旅行时,基本的状态转移方程就是:
$$dp(i) = \min {\lbrace dp(i - 1) + costs[0],\ dp(i - 7) + costs[1],\ dp(i - 30) + costs[2] \rbrace}$$
当天不需要旅行时,状态转移方程就是:
$$dp(i) = \min {\lbrace dp(i - 1),\ dp(i - 7) + costs[1],\ dp(i - 30) + costs[2] \rbrace}$$
注意:
- i 从小到大进行递推
- 当天可能无需旅行,就无需买一天的通行证,但是扔可能之前购买了 7 或 30 天的购买通行证,需要分类讨论
- dp(i - 1) 等可能下溢,则结果直接定为 0 即可
解法二
不妨逆向思维,且利用贪心思路定义 dp(i) 为计划在第 i 天支出的车票花费,以方便之后的旅行,这样最后原问题答案就是 dp(1)。 如果当天需要旅行,相应的状态转移方程就是:
$$dp(i) = \min {\lbrace dp(i + 1) + costs[0],\ dp(i + 7) + costs[1],\ dp(i + 30) + costs[2] \rbrace}$$
如果当天无需旅行,则就有:
$$dp(i) = dp(i + 1)$$
注意:
- i 从大到小递推
- 无需旅行的时候,后续大于 i 时已经进行好了计划,所以直接使用之后的花费计划即可
- dp(i + 1) 等可能上溢,结果就是 0
代码
我们会频繁地查询某一天是否需要旅行,可以使用哈希表储存 days 的内容,当然也可以使用桶。
解法一:
|
|
解法二:
|
|