Sponsored
Sponsored
This approach uses dynamic programming to maintain a cost array where each cell represents the minimum cost to travel up to that day. For each travel day, you decide to either buy a 1-day, 7-day, or 30-day pass and record the cost accordingly.
Time Complexity: O(n) where n is the last travel day. Space Complexity: O(n) for the DP array.
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 int mincostTickets(std::vector<int>& days, std::vector<int>& costs) {
7 int n = days.back();
8 std::vector<int> dp(n + 1, 0);
9 std::vector<bool> travelDay(n + 1, false);
10 for (int day : days) travelDay[day] = true;
11 for (int i = 1; i <= n; i++) {
12 if (!travelDay[i]) {
13 dp[i] = dp[i - 1];
14 } else {
15 dp[i] = std::min({
16 dp[i - 1] + costs[0],
17 dp[i - 7 < 0 ? 0 : i - 7] + costs[1],
18 dp[i - 30 < 0 ? 0 : i - 30] + costs[2]
19 });
20 }
21 }
22 return dp[n];
23 }
24};The C++ solution uses a similar dynamic programming strategy as the C solution, but it also maintains a boolean array to check if the current day is a travel day, thus optimizing unnecessary checks.
This approach uses recursion with memoization to explore each travel day recursively, storing intermediate results to avoid redundant calculations. It offers a top-down perspective on decision-making for ticket purchasing.
Time Complexity: O(n) where n is the number of travel days due to memoization. Space Complexity: O(n) for the memo array.
1
This C implementation uses recursive depth-first search (DFS) with memoization to explore and store results of subproblems, reducing redundant calculations. The function calculates the minimum cost by considering costs of possible travel passes starting at each travel day index.