LeetCode 983 最低票价

2020-05-06 2020-05-06 约 1150 字预计阅读 3 分钟

本题属于典型的动态规划题目，而且还有不止一种做法，又能与贪心算法有所联系，算是一道比较优秀的题目。

题目描述

题目大意

火车票实行多种不同的通行证方案，购买一个通行证后，在方案规定的天数内可随意乘车，无需再缴费。例如：如果我们在第 2 天获得一张为期 7 天的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。同时，我们一年内可能在不同的日子都要进行铁路旅行，那么就可以使用多种不同的通行证购买方案，但是根据其价格和时长总会有个花费最少的方案，本题就是要求出这个最少花费。

输入与输出

在接下来的一年（记为 365 天）里，你要旅行的日子储存再一个名为 days 的数组里，数组每一项是一个从 1 到 365 的整数。火车票有三种价格，记录在长度为 3 的 costs 数组种，数组元素对应不同的通行证时长，分别为：1 天、7 天和 30 天。

示例输入为：

1
2
3
4
5
6
7
Input 1:
days = [1,4,6,7,8,20]
costs = [2,7,15]

Input 2:
days = [1,2,3,4,5,6,7,8,9,10,30,31]
costs = [2,7,15]

days 按顺序严格递增，且不会重复

示例输出为：

1
2
3
4
5
Output 1:
11

Output 2:
17

解题思路

本题明显可以采用动态规划方法求解，而且题目子问题也容易表达，但是仍然会有两种不同的规划方案供选择。

解法一

直观地定义状态 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 的内容，当然也可以使用桶。

解法一：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    fun mincostTickets(days: IntArray, costs: IntArray): Int {
        if (days.isEmpty()) return 0
        val last = days.last()
        val daySet = days.toSet()
        val dp = IntArray(last + 1)
        for (i in 1..last) {
            var minCost = if (i in daySet) dp[i - 1] + costs[0] else dp[i - 1]
            minCost = if (i > 7) minOf(minCost, dp[i - 7] + costs[1]) else minOf(minCost, costs[1])
            minCost = if (i > 30) minOf(minCost, dp[i - 30] + costs[2]) else minOf(minCost, costs[2])
            dp[i] = minCost
        }
        return dp[last]
    }
}

解法二：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    fun mincostTickets(days: IntArray, costs: IntArray): Int {
        if (days.isEmpty()) return 0
        val last = days.last()
        val daySet = days.toSet()
        val dp = IntArray(last + 1)
        for (i in last downTo 1) {
            if (i !in daySet) {
                dp[i] = if (i < last) dp[i + 1] else 0
                continue
            }
            var min = costs[0] + if (i + 1 > last) 0 else dp[i + 1]
            min = minOf(min, costs[1] + if (i + 7 > last) 0 else dp[i + 7])
            min = minOf(min, costs[2] + if (i + 30 > last) 0 else dp[i + 30])
            dp[i] = min
        }
        return dp[1]
    }
}

目录

LeetCode 983 最低票价

题目描述

题目大意

输入与输出

解题思路

解法一

解法二

代码