【leetcode】983.最低票价js

题目

代码-基于自然日

定义dp数组

dp[i] = 从第 i 天（包含第 i 天）到最后一天，覆盖所有旅行日，最少要花多少钱。

例如最后一天是365天的话，则:

dp[366] = 0（年底之后，不用花钱）

dp[100] = 从第 100 天开始到 365 天，覆盖所有旅行日的最少花费。

找规律（转移方程）

站在第 i 天，我们分两种情况：

情况 A：第 i 天不旅行（不在 days 数组里）

• 既然不用出门，今天一分钱不花。

• 明天的花费和今天一样，所以：

  dp[i] = dp[i + 1]
  （直接把明天的结果抄过来）

情况 B：第 i 天要旅行（在 days 数组里）

• 今天必须解决出行，有三张票可以选，三选一，取最便宜的：

• 买 1 天票（花 costs[0] 元）
  覆盖今天（第 i 天），明天（第 i+1 天）开始重新算。
  → 总花费 = costs[0] + dp[i + 1]

• 买 7 天票（花 costs[1] 元）
  覆盖今天 + 未来 6 天（第 i 天 到 第 i+6 天）。
  第 i+7 天开始重新算。
  → 总花费 = costs[1] + dp[i + 7]

• 买 30 天票（花 costs[2] 元）
  覆盖今天 + 未来 29 天（第 i 天 到 第 i+29 天）。
  第 i+30 天开始重新算。
  → 总花费 = costs[2] + dp[i + 30]

所以旅行日取三者最小值：

dp[i] = min( costs[0]+dp[i+1], costs[1]+dp[i+7], costs[2]+dp[i+30] )

代码实现

/**
* @param {number[]} days
* @param {number[]} costs
* @return {number}
*/
var mincostTickets = function(days, costs) {
const maxDay = days[days.length – 1]
// 边界处理，最后一天就算要买一张三十天的票也不会越界
const dp = new Array(maxDay + 31).fill(0)
// 用来存需要旅行的日子
const travelDay = new Set(days)

for (let i = maxDay; i >= 1; i–) {
if (travelDay.has(i)) {
dp[i] = Math.min(
costs[0] + dp[i + 1],
costs[1] + dp[i + 7],
costs[2] + dp[i + 30]
)
} else {
dp[i] = dp[i + 1]
}
}
return dp[1]
};

代码-基于旅行日索引

定义dp数组

dp[i] 表示：处理完 days 数组中的前 i 个旅行日，所花的最少钱。

状态转移方程

只关心“最后一个旅行日”是怎么被覆盖的。

1. 最后一张票买“1天票”（最朴素的情况）

• 既然只覆盖今天，那么今天的钱单独出，前面的 i-1 天照旧。

• 所以：dp[i] = dp[i-1] + costs[0]（代码第一句默认就是这个）。

2. 最后一张票买“7天票”

• 这张 7 天票覆盖了今天以及往前推的若干天。

• 我们要往前找，找到第一个没有被这张 7 天票覆盖到的旅行日。

• 假设这个“没被覆盖到的最后一天”的下标是 j，那么 0 到 j 这些天需要靠之前的票解决（即 dp[j+1]），而 j+1 到 i-1 这些天全被这张 7 天票包圆了。

• 所以：dp[i] = Math.min(dp[i], dp[j+1] + costs[1])

3. 最后一张票买“30天票”

• 逻辑完全同上，只是把 7 换成 30。

代码实现

/**
* @param {number[]} days
* @param {number[]} costs
* @return {number}
*/
var mincostTickets = function(days, costs) {
const dp = new Array(days.length + 1).fill(0)
for (let i = 1; i <= days.length; i++) {
dp[i] = dp[i -1] + costs[0]

let j = i – 1
while (j >= 0 && days[i – 1] – days[j] < 7) j–
dp[i] = Math.min(dp[i], dp[j + 1] + costs[1])

j = i – 1
while (j >= 0 && days[i – 1] – days[j] < 30) j–
dp[i] = Math.min(dp[i], dp[j + 1] + costs[2])
}
return dp[days.length]
};

举例说明

let j = i – 1
while (j >= 0 && days[i – 1] – days[j] < 7) j–
dp[i] = Math.min(dp[i], dp[j + 1] + costs[1])

假设 days = [1, 4, 6, 10]，现在 i = 4（当前日期是 10），买 7 天票：

此时 j = 0。
这意味着：下标 0（日期 1）没有被这张 7 天票覆盖到。
dp[j + 1] = dp[1]，表示前 1 个旅行日（日期 1）需要单独花钱解决。
而后面的 1,2,3（日期 4,6,10）全部被这张 7 天票覆盖。
所以总花费 = dp[1] + costs[1]。

默认买单日票

先假设“今天单独买一张 1 天票”。
然后后面的 Math.min 只是拿“7天票”和“30天票”的方案去挑战这个默认值，谁小就留谁。
这样写的好处是不需要单独判断今天是不是旅行日，因为 dp 只针对旅行日建表，循环到的每一天一定都在 days 里。