Bus Fare

https://binarysearch.com/problems/Bus-Fare

题目描述

You are given a list of sorted integers days , where you must take the bus for on each day. Return the lowest cost it takes to travel for all the days.

There are 3 types of bus tickets.

1 day pass for 2 dollars
7 day pass for 7 dollars
30 day pass for 25 dollars
Constraints

n ≤ 100,000 where n is the length of days
Example 1
Input
days = [1, 3, 4, 5, 29]
Output
9
Explanation
The lowest cost can be achieved by purchasing a 7 day pass in the beginning and then a 1 day pass on the 29th day.

Example 2
Input
days = [1]
Output
2

前置知识

• 递归树

• 多指针

公司

• 暂无

暴力 DP

思路

定义专状态 dp[i] 为截止第 i + 1 天（包括）需要多少钱，因此答案就是 dp[n]，其中 n 为 max(days)，由于 day 是升序的，因此就是 day 最后一项。

使用两层暴力寻找。外层控制 i 天， 内层循环控制 j 天，其中 i <= j。每次我们只考虑进行一次操作：

• 买一张天数 2 的票

• 买一张天数 7 的票

• 买一张天数 25 的票

对于每一个 [i, j]对，我们对计算一遍，求出最小值就可以了。

代码：

class Solution:
    def solve(self, days):
        n = len(days)
        prices = [2, 7, 25]
        durations = [1, 7, 30]
        dp = [float("inf")] * (n + 1)
        dp[0] = 0

        for i in range(1, n + 1):
            for j in range(i, n + 1):
                # 如何第 i + 1天到第 j 天的天数小于等于 2，那么我们就试一下在 i + 1 天买一张 2 天的票，看会不会是最优解。
                # 7 和 25 的逻辑也是一样
        return dp[-1]

代码

代码支持：Python3

Python3 Code:

class Solution:
    def solve(self, days):
        n = len(days)
        prices = [2, 7, 25]
        durations = [1, 7, 30]
        dp = [float("inf")] * (n + 1)
        # dp[i] 表示截止第 i + 1 天（包括）需要多少钱，因此答案就是 dp[n]，其中 n 为 max(days)，由于 day 是升序的，因此就是 day 最后一项。
        dp[0] = 0

        for i in range(1, n + 1):
            for j in range(i, n + 1):
                for price, duration in zip(prices, durations):
                    if days[j - 1] - days[i - 1] + 1 <= duration:
                        dp[j] = min(dp[j], dp[i - 1] + price)
        return dp[-1]

复杂度分析

令 m 和 n 分别为 prices 和 days 的长度。

• 时间复杂度：$O(m * n^2)$

• 空间复杂度：$O(n)$

多指针优化

思路

这种算法需要枚举所有的 [i,j] 组合，之后再枚举所有的票，这无疑是完备的，但是复杂度很高。需要进行优化，接下来我们看下如何进行优化。

由于不同的票价的策略是一致的，因此我们可以先仅考虑天数为 2 的。 假如两天的票内层循环的 j 找到了第一个满足条件的 i，不妨假设 i 的值是 x。

那么下一次循环，i 指针不必从 0 开始，而是直接从 x 开始，因此 x 之前肯定都无法满足： days[j - 1] - days[i - 1] + 1 <= duration。这是优化的关键，这点其实和《组成三角形的个数》题目类似。关键都在于指针不回退，达到优化的效果。 实际上，思想上来看单调栈也是类似的。

上面我说了是 i 不回退，实际上不同的天数的票对应的上一次指针位置是不同的，我们可以使用一个长度为 m 的指针数组来表示不同天数的票上一次 i 指针的位置。相比于双指针，多指针的编码会稍微复杂一点。

由于 i 指针不需要回退，因此省略了一层 n 的循环，时间复杂度可以从 $O(m n^2)$ 降低到 O(m \ n)$。

代码

代码支持：Python3

Python3 Code:

class Solution:
    def solve(self, days):
        prices = [2, 7, 25]
        durations = [1, 7, 30]
        n = len(days)
        m = len(prices)
        dp = [float("inf")] * (n + 1)
        dp[0] = 0
        pointers = [0] * m
        for i in range(1, n + 1):
            for j in range(m):
                while days[i - 1] - days[pointers[j]] >= durations[j]:
                    pointers[j] += 1
                dp[i] = min(dp[i], dp[pointers[j]] + prices[j])
        return dp[-1]

复杂度分析

令 m 和 n 分别为 prices 和 days 的长度。

• 时间复杂度：$O(m * n)$

• 空间复杂度：$O(m + n)$