算法
February 4, 2019

LeetCode-Minimum Cost for Tickets

Minimum Cost For Tickets

题目描述

LeetCode地址：983. Minimum Cost For Tickets

In a country popular for train travel, you have planned some train travelling one year in advance. The days of the year that you will travel is given as an array days. Each day is an integer from 1 to 365.

Train tickets are sold in 3 different ways:

The passes allow that many days of consecutive travel. For example, if we get a 7-day pass on day 2, then we can travel for 7 days: day 2, 3, 4, 5, 6, 7, and 8.

Return the minimum number of dollars you need to travel every day in the given list of days.

days数组中存储的是该年中去旅游的日期（范围为1到365之间的数字），costs数组大小为3，存储的是1天，7天和30天火车票的价格。我们需要做一个方案选择合适的购票方案达到旅游days天最省钱的目的。

算法描述

采用动态规划进行解决，假设现在是第days[i]天，我们在该天出行旅游需要选择买票方案，现在我们有三种方案：第一，购买一天的通行票，当天出行，花费就是第days[i-1]天的花费加上一天的通行票价；第二，购买七天的通行票，而七天的通行票可以在连续的七天之内使用，所以花费是第days[i-7]天的花费加上七天的通行票价（即从第days[i-8]天到days[i]天的花费都包含在这七天的通行票中）；第三，购买三十天的通行票，同理，花费是days[i-30]天加上三十天的通行票价。然后我们在这三种方案中选择最实惠的。最后，在实现代码中注意数组越界的问题。

使用dp[j]代表着我们旅行到i天为止需要的最少旅行价格，递推公式为：

  1. dp[j] = dp[j-1] （第j天不用旅行）
  2. dp[j] = min(dp[j-1] + costs[0], dp[j-7] + costs[1], dp[j-30] + costs[2]) （第j天需要旅行）

C++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int mincostTickets(vector<int> &days, vector<int> &costs) {
        if (days.size() == 0) return 0;
        assert(costs.size() == 3);
        // dp[i]代表着我们旅行到i天需要的最少旅行价格, dp[0]为0，没实际含义
        array<int, 366> dp = {0};
        for (int i = 1; i < dp.size(); ++i) {
            // 如果这一天不旅行
            if (find(days.begin(), days.end(), i) == days.end()) dp[i] = dp[i - 1];
            else {
                dp[i] = min({
                   dp[i - 1] + costs[0],
                   dp[max(0, i - 7)] + costs[1],
                   dp[max(0, i - 30)] + costs[2]
                });
            }
        }
        return dp[365];
    }
};

Scala实现

注：如果有童鞋有纯函数的实现，希望分享出来！共享！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
object Solution {
  def mincostTickets(days: Array[Int], costs: Array[Int]): Int = {
    if (days.length == 0) return 0
    assert(costs.length == 3)
    val travels = days.toSet
    val dp = Array.fill[Int](366)(0)

    for (i <- 1 until 366) {
      if (!travels.contains(i)) dp(i) = dp(i - 1)
      else dp(i) = List(
        dp(i - 1) + costs(0),
        dp(math.max(0, i - 7)) + costs(1),
        dp(math.max(0, i - 30)) + costs(2)
      ).min
    }

    dp(365)
  }
}