You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

983. 最低票价 - Minimum Cost For Tickets

. 3 min read

【动态规划】

在一个火车旅行很受欢迎的国度,你提前一年计划了一些火车旅行。在接下来的一年里,你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1365 的整数。

火车票有三种不同的销售方式:

  • 一张为期一天的通行证售价为 costs[0] 美元;
  • 一张为期七天的通行证售价为 costs[1] 美元;
  • 一张为期三十天的通行证售价为 costs[2] 美元。

通行证允许数天无限制的旅行。 例如,如果我们在第 2 天获得一张为期 7 天的通行证,那么我们可以连着旅行 7 天:第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费。

Example:

示例 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. 1 <= days.length <= 365
  2. 1 <= days[i] <= 365
  3. days 按顺序严格递增
  4. costs.length == 3
  5. 1 <= costs[i] <= 1000

Solutions

Solution 【动态规划】 ( 6ms)

class Solution {
  public int mincostTickets(int[] days, int[] costs) {
    int[] minCosts = new int[days[days.length - 1] + 1];
    Set<Integer> daySet = new HashSet<>();
    for (int day : days) {
      daySet.add(day);
    }
    int ticket1 = costs[0];
    int ticket7 = costs[1];
    int ticket30 = costs[2];
    for (int i = 1, length =  minCosts.length; i < length; i++) {
      if (!daySet.contains(i)) {
        minCosts[i] = minCosts[i - 1];
        continue;
      }
      minCosts[i] = getMinOfThree(
          minCosts[i - 1] + ticket1, 
          minCosts[Math.max(0, i - 7)] + ticket7, 
          minCosts[Math.max(0, i - 30)] + ticket30);
    }
    return minCosts[minCosts.length - 1];
  }

  private int getMinOfThree(int a, int b, int c) {
    int result = a < b ? a : b;
    if (c < result) {
      result = c;
    }
    return result;
  }
}

复杂度分析

Solution 【动态规划】 ( 4ms)

class Solution {
        public int[] dp = new int[366];
        public int[] costs;
        public int r(int[] days, int i, int cur){
            if(cur <= days[0]){
                return 0;
            }
            if(dp[cur] != 0){
                return dp[cur];
            }
            while (days[i] >= cur){
                i--;
            }
            int a = r(days, i, days[i]) + costs[0];
            int b = r(days, i, days[i] - 6) + costs[1];
            int c = r(days, i, days[i] - 29) + costs[2];
            int min = Math.min(a,Math.min(b,c));
            dp[cur] = min;
            return min;
        }
        public int mincostTickets(int[] days, int[] costs) {
            this.costs = costs;
            return r(days,days.length - 1, days[days.length - 1] + 1);
        }
    }

Notes

Reference