Question

983. 最低票价

English Version

题目描述

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 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

解法

方法一：记忆化搜索 + 二分查找

定义 $dfs(i)$ 表示从第 $i$ 次出行开始的最低消费。答案为 $dfs(0)$。

采用记忆化搜索的方法，记录已经计算过的结果，避免重复计算。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为 days 的长度。

class Solution:
  def mincostTickets(self, days: List[int], costs: List[int]) -> int:
    @cache
    def dfs(i):
      if i >= len(days):
        return 0
      res = inf
      for c, d in zip(costs, [1, 7, 30]):
        j = bisect_left(days, days[i] + d)
        res = min(res, c + dfs(j))
      return res

    return dfs(0)

class Solution {
  private static final int[] T = new int[] {1, 7, 30};
  private int[] costs;
  private int[] days;
  private int[] f;
  private int n;

  public int mincostTickets(int[] days, int[] costs) {
    n = days.length;
    f = new int[n];
    this.costs = costs;
    this.days = days;
    Arrays.fill(f, -1);
    return dfs(0);
  }

  private int dfs(int i) {
    if (i >= n) {
      return 0;
    }
    if (f[i] != -1) {
      return f[i];
    }
    int res = Integer.MAX_VALUE;

    for (int k = 0; k < 3; ++k) {
      int j = lowerBound(days, days[i] + T[k]);
      res = Math.min(res, costs[k] + dfs(j));
    }
    f[i] = res;
    return res;
  }

  private int lowerBound(int[] days, int x) {
    int left = 0, right = days.length;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (days[mid] >= x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

class Solution {
public:
  vector<int> t = {1, 7, 30};
  vector<int> days;
  vector<int> costs;
  vector<int> f;
  int n;

  int mincostTickets(vector<int>& days, vector<int>& costs) {
    n = days.size();
    this->days = days;
    this->costs = costs;
    f.assign(n, -1);
    return dfs(0);
  }

  int dfs(int i) {
    if (i >= n) return 0;
    if (f[i] != -1) return f[i];
    int res = INT_MAX;
    for (int k = 0; k < 3; ++k) {
      int j = lower_bound(days.begin(), days.end(), days[i] + t[k]) - days.begin();
      res = min(res, costs[k] + dfs(j));
    }
    f[i] = res;
    return res;
  }
};

func mincostTickets(days []int, costs []int) int {
  t := []int{1, 7, 30}
  n := len(days)
  f := make([]int, n)
  for i := range f {
    f[i] = -1
  }
  var dfs func(i int) int
  dfs = func(i int) int {
    if i >= n {
      return 0
    }
    if f[i] != -1 {
      return f[i]
    }
    res := 0x3f3f3f3f
    for k, c := range costs {
      j := lowerBound(days, days[i]+t[k])
      res = min(res, c+dfs(j))
    }
    f[i] = res
    return res
  }
  return dfs(0)
}

func lowerBound(arr []int, x int) int {
  left, right := 0, len(arr)
  for left < right {
    mid := (left + right) >> 1
    if arr[mid] >= x {
      right = mid
    } else {
      left = mid + 1
    }
  }
  return left
}

function mincostTickets(days: number[], costs: number[]): number {
  const n = days.length,
    m = days[n - 1] + 1;
  const [a, b, c] = costs;
  let dp = new Array(m).fill(0);
  for (let i = 1; i < m; i++) {
    let x = days.includes(i) ? dp[i - 1] + a : dp[i - 1];
    let y = (i > 7 ? dp[i - 7] : dp[0]) + b;
    let z = (i > 30 ? dp[i - 30] : dp[0]) + c;
    dp[i] = Math.min(x, y, z);
  }
  return dp[m - 1];
}