Minimum Cost For Tickets

小鱼儿 2022-04-23 09:06 138阅读 0赞

### 文章目录 ###

*  Minimum Cost For Tickets
 *   *  题目描述
     *  算法描述
     *  C++实现
     *  Scala实现

# 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:

*  a 1-day pass is sold for `costs[0]` dollars;
 *  a 7-day pass is sold for `costs[1]` dollars;
 *  a 30-day pass is sold for `costs[2]` dollars.

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++实现 ##

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实现 ##

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

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)
      }
    }

[983. Minimum Cost For Tickets]: https://leetcode.com/problems/minimum-cost-for-tickets/