Leetcode983. 最低票价

Every day a Leetcode

题目来源：983. 最低票价

解法1：记忆化搜索

定义 dfs(i) 表示 1 到 i 天的最小花费。

如果第 i 天不在 days 中，那么问题变成 1 到 i−1 天的最小花费，即：dfs(i)=dfs(i−1)。

如果第 i 天在 days 中，分类讨论：

• 在第 i 天购买为期 1 天的通行证，接下来需要解决的问题为：1 到 i−1 天的最小花费，即 dfs(i)=dfs(i−1)+costs[0]。
  在第 i−6 天购买为期 7 天的通行证，接下来需要解决的问题为：1 到 i−7 天的最小花费，即 dfs(i)=dfs(i−7)+costs[1]。
  在第 i−29 天购买为期 30 天的通行证，接下来需要解决的问题为：1 到 i−30 天的最小花费，即 dfs(i)=dfs(i−30)+costs[2]。

这三种情况取最小值，就得到了 dfs(i)。

代码：

#
# @lc app=leetcode.cn id=983 lang=python3
#
# [983] 最低票价
## @lc code=start
class Solution:def mincostTickets(self, days: List[int], costs: List[int]) -> int:hashSet = set(days)@cachedef dfs(i: int) -> int:if i <= 0:return 0if i not in hashSet:return dfs(i - 1)return min(dfs(i - 1) + costs[0], dfs(i - 7) + costs[1], dfs(i - 30) + costs[2])return dfs(days[-1])      
# @lc code=end

结果：

复杂度分析：

时间复杂度：O(D)，其中 D=days[n−1]，n 为数组 days 的长度。

空间复杂度：O(D)，其中 D=days[n−1]，n 为数组 days 的长度。

解法2：动态规划

代码：

/** @lc app=leetcode.cn id=983 lang=cpp** [983] 最低票价*/// @lc code=start
class Solution
{
public:int mincostTickets(vector<int> &days, vector<int> &costs){int lastDay = days[days.size() - 1];vector<int> dp(lastDay + 1);unordered_set<int> hashSet(days.begin(), days.end());// 初始化dp[0] = 0;// 状态转移for (int i = 1; i <= lastDay; i++){if (!hashSet.contains(i))dp[i] = dp[i - 1];elsedp[i] = min({dp[i - 1] + costs[0],dp[max(i - 7, 0)] + costs[1],dp[max(i - 30, 0)] + costs[2]});}return dp[lastDay];}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(D)，其中 D=days[n−1]，n 为数组 days 的长度。

空间复杂度：O(D)，其中 D=days[n−1]，n 为数组 days 的长度。