跳至主要內容

最低票价

linwu大约 1 分钟

最低票价

题目描述

给定一组旅行日期 days 和对应的票价 costs,你需要购买一张车票以完成整个旅行。车票有三种不同的类型:1 天通行证、7 天通行证和 30 天通行证。我们可以按任意顺序购买这些通行证。

请你计算完成旅行所需的最低票价。

解题步骤

为了解决最低票价问题,我们可以使用动态规划的思想来解决。

  1. 定义状态:我们使用一个数组 dp 来表示最低票价,其中 dp[i] 表示在第 i 天需要的最低票价。
  2. 初始化状态:我们将 dp 数组初始化为一个长度为 days.length + 1 的数组,初始值为 Infinity,表示在旅行结束后的一天,我们不需要再购买任何车票。
  3. 定义状态转移方程:对于每一天 i,我们有三种选择:
    • 如果这一天不需要旅行,那么 dp[i] 等于前一天的最低票价,即 dp[i] = dp[i-1]
    • 如果这一天需要旅行,我们可以考虑购买 1 天、7 天或 30 天的通行证。我们选择最低的票价作为当前的最低票价。即 dp[i] = Math.min(dp[i], dp[i-1] + costs[0], dp[i-7] + costs[1], dp[i-30] + costs[2])
  4. 最终结果:dp[days.length] 即为完成整个旅行所需的最低票价。

下面是使用动态规划解决最低票价问题的算法框架:

function mincostTickets(days, costs) {
  const dp = new Array(days.length + 1).fill(Infinity);
  dp[0] = 0;

  for (let i = 1; i <= days.length; i++) {
    if (!days.includes(i)) {
      dp[i] = dp[i - 1];
    } else {
      dp[i] = Math.min(
        dp[i - 1] + costs[0],
        dp[Math.max(i - 7, 0)] + costs[1],
        dp[Math.max(i - 30, 0)] + costs[2]
      );
    }
  }

  return dp[days.length];
}

关注公众号

和小伙伴们一起学习

加入技术交流群

扫描二维码 备注加群