题目描述
在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。
在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。
每一项是一个从 1 到 365 的整数。
火车票有 三种不同的销售方式 ：
- 一张 为期一天 的通行证售价为
costs[0]美元； - 一张 为期七天 的通行证售价为
costs[1]美元； - 一张 为期三十天 的通行证售价为
costs[2]美元。
通行证允许数天无限制的旅行。
例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，
那么我们可以连着旅行 7 天：
- 第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。
- 返回
- 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费
示例 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 <= days.length <= 365
1 <= days[i] <= 365
days 按顺序严格递增
costs.length == 3
1 <= costs[i] <= 1000题目解析
个人思路历程
- 首先理解
days数组，days[i]：表示了在一年中的这一天计划出游
- 计划出游的话那么肯定需要买票
- 因此最基本的出游的每一天都需要买票：
总花费 = days.length * costs[0]
costs[0]表示为期一天的通行证售价
- 那么如何找到最优解呢？
- 题目标签是动态规划，那么需要思考 base case
- 令
n = days.length创建 dp 数组int[] dp = new int[n + 1]; - 思考
dp[0]的意义：表示不出去旅行的花费是多少——很显然dp[0] = 0 - 那么
dp[1] = costs[0]: 出去旅行一天，买一张 一天的通行证 dp[2] = costs[0] * 2- 那么这个时候考虑一个问题，什么时候买七天的通行证会比较划算。
k = cost[1] / cost[0] = 7 / 2 = 3- 当出游 3 天的时候，即使 7 天通行证能够覆盖，还是 一天一天买比较合算
- 所以 7 天通行证覆盖天数 要 大于 k
dp[3] = costs[3] * 3dp[4] = ?：判断七天通行证是否能够覆盖dp[5] = ?：好像有点偏了，不好继续了
参考官解之后总结
- 假设要计划统计一年中旅行出游的总花费，那么问题产生
- 从第一天开始统计计算
- 很显然结合题目，需要从最后一天开始统计计算
- 从最后一天开始统计计算
- 结合
days数组 - 依次判断
- 第
365天是否需要出游，如果不出游，那么其花销和第364天一样
- 如果出游，那么是否需要买票呢？
- 已知有三种火车票：
有效期 = 1/7/30天 - 那么存在情况：如果第
335天购买了30天的票，第 365 天则不需要购票
- 那么对于 第
i天的花费，有如下结论 - 不出游：
dp[i] = dp[i + 1] - 出游：
记忆优化搜索
class Solution {
int[] costs;
int[] memo;
Set<Integer> daySet;
public int mincostTickets(int[] days, int[] costs) {
// 初始化一个 对应一年天数的数组.
memo = new int[366];
// 初始化一个值
Arrays.fill(memo, -1);
this.costs = costs;
daySet = new HashSet<>();
for(int day : days) {
daySet.add(day);
}
return dfs(1);
}
private int dfs(int i) {
if(i > 365) {
return 0;
}
if(memo[i] != -1) {
return memo[i];
}
if(daySet.contains(i)) {
int oneCost = costs[0] + dfs(i + 1);
int sevenCost = costs[1] + dfs(i + 7);
int thirtyCost = costs[2] + dfs(i + 30);
memo[i] = Math.min(oneCost, Math.min(sevenCost, thirtyCost));
} else {
memo[i] = dfs(i + 1);
}
return memo[i];
}
}1:1 递推
class Solution {
public int mincostTickets(int[] days, int[] costs) {
// 总天数
int n = days.length;
// 最小/最大天数
int minDay = days[0],maxDay = days[n - 1];
// 创建 dp 数组
int[] dp = new int[maxDay + 31];
// i : days 索引
for(int day = maxDay,i = n - 1;day >= minDay;day--) {
// 当天需要出游
if(day == days[i]) {
dp[day] = Math.min(dp[day + 7] + costs[1], dp[day + 30] + costs[2]);
dp[day] = Math.min(dp[day + 1] + costs[0], dp[day]);
i--;
} else {
dp[day] = dp[day + 1];
}
}
return dp[minDay];
}
}