湘潭网站建设 要上磐石网络,网站建设与网页设计入门,apache wordpress 404,养老网站建设【问题描述】[第983题][最低票价][中等]
在一个火车旅行很受欢迎的国度#xff0c;你提前一年计划了一些火车旅行。在接下来的一年里#xff0c;你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。火车票有三种不同的销售方式#xff1a;一张为…【问题描述】[第983题][最低票价][中等]
在一个火车旅行很受欢迎的国度你提前一年计划了一些火车旅行。在接下来的一年里你要旅行的日子将以一个名为 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并完成了你计划的每一天旅行。
【解答思路】
1. 动态规划 第 1 步设计状态 int[] dp new int[maxDay 31]; 第 2 步状态转移方程
第 3 步考虑初始化 从后往前思考
第 4 步考虑输出 时间复杂度O(N) 空间复杂度O(n)
class Solution {public int mincostTickets(int[] days, int[] costs) {int len days.length, maxDay days[len - 1], minDay days[0];int[] dp new int[maxDay 31]; // 多扩几天省得判断 365 的限制// 只需看 maxDay - minDay此区间外都不需要出门不会增加费用for (int d maxDay, i len - 1; d minDay; d--) {// i 表示 days 的索引// 也可提前将所有 days 放入 Set再通过 set.contains() 判断if (d days[i]) {dp[d] Math.min(dp[d 1] costs[0], dp[d 7] costs[1]);dp[d] Math.min(dp[d], dp[d 30] costs[2]);i--; // 别忘了递减一天} else dp[d] dp[d 1]; // 不需要出门}return dp[minDay]; // 从后向前遍历返回最前的 minDay}
}
【总结】
1. 动态规划流程
第 1 步设计状态 第 2 步状态转移方程 第 3 步考虑初始化 第 4 步考虑输出 第 5 步考虑是否可以状态压缩
2. 动态规划 从后往前 从前往后
3. 动态规划想好子问题
转载链接https://leetcode-cn.com/problems/minimum-cost-for-tickets/solution/java-dong-tai-gui-hua-si-lu-bu-zou-cong-hou-xiang-/
