983.最低票价

链接：983.最低票价
难度：Medium
标签：数组、动态规划
简介：在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为  days  的数组给出。每一项是一个从  1  到  365  的整数。

题解 1 - javascript

• 编辑时间：2020-05-06
• 执行用时：208ms
• 内存消耗：38.2MB
• 编程语言：javascript
• 解法介绍：回溯+剪枝，递归判断每次遍历的值，通过 cache 储存计算过的值。

/**
 * @param {number[]} days
 * @param {number[]} costs
 * @return {number}
 */
var mincostTickets = function (days, costs) {
  const len = days.length;
  const costDays = [1, 7, 30];
  const lastDay = days[len];
  const cache = {};
  return getMin(0, 0);
  function getMin(start, maxDay) {
    if (cache[format(start, maxDay)]) return cache[format(start, maxDay)];
    while (start < len && days[start] < maxDay) start++;
    if (start === len || lastDay <= maxDay) return 0;
    let minCost = 999999;
    if (days[start] > maxDay)
      for (let j = 0; j < 3; j++) {
        const cost = costs[j];
        minCost = Math.min(getMin(start + 1, days[start] + costDays[j] - 1) + cost, minCost);
      }
    else minCost = getMin(start + 1, maxDay);
    cache[format(start, maxDay)] = minCost;
    return minCost;
  }
  function format(start, maxDay) {
    return `${start}-${maxDay}`;
  }
};

题解 2 - python

• 编辑时间：2024-10-01
• 执行用时：47ms
• 内存消耗：18.82MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        @cache
        def walk(idx: int, last: int) -> int:
            if idx == len(days): return 0
            day = days[idx]
            if day <= last: return walk(idx + 1, last)
            return min(
                walk(idx + 1, day + 1 - 1)  + costs[0],
                walk(idx + 1, day + 7 - 1)  + costs[1],
                walk(idx + 1, day + 30 - 1) + costs[2],
            )
        return walk(0, -1)