长大后想做什么？做回小孩！

0%

LeetCode——最低票价

发表于 分类于 Valine：
本文字数： 489

NO.983 最低票价 中等

YkOY6J.png

YkOJl4.png

思路一：动态规划 从后向前判断，第 i 日应该如何购买。

dp[day]的含义：从第 day 天开始，累计需要购买的通行证的最小费用，只需要向后看 30 天内的购买方案即可。

初始化：dp[maxday + 31]，最大日期多增加一个月，因为第 maxday 还要向后看 30 天。

状态转移：计算 [minday,maxday] 区间内的每一天 day ，如果第 day 天不需要旅行，那么从第 day 天不需要购买通行证，dp[day]=dp[day+1]；

如果第 day 天需要旅行，那么有三种方案：

  1. 当天买一个 1 天的通行证，dp[day]=costs[0]+dp[day+1]
  2. 当天买一个 7 天的通行证，dp[day]=costs[1]+dp[day+7]
  3. 当天买一个 30 天的通行证，dp[day]=costs[1]+dp[day+30]

三种方案选”实惠”的：dp[day]=Min(costs[0]+dp[day+1],costs[1]+dp[day+7],costs[1]+dp[day+30])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int mincostTickets(int[] days, int[] costs) {
    int minDay = days[0], maxDay = days[days.length - 1];
    int[] dp = new int[maxDay + 31];
    //days 数组索引
    int i = days.length - 1;
    //计算 [minDay,maxDay] 区间内的每一天
    for (int day = maxDay; day >= minDay; day--) {
        //第 day 天需要旅行
        if (day == days[i]) {
            //三种方案
            dp[day] = Math.min(costs[0] + dp[day + 1],
                               Math.min(costs[1] + dp[day + 7], costs[2] + dp[day + 30]));
            // days[i]计算完毕
            i--;
        } else {
            //第 day 天不需要旅行 dp[day]=0+dp[day + 1]
            dp[day] = dp[day + 1];
        }
    }
    return dp[minDay];
}

时间复杂度：O(maxDay-minDay)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github