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 <stdio.h>
2
3int mincostTickets(int* days, int daysSize, int* costs, int costsSize) {
4 int n = days[daysSize - 1];
5 int dp[n + 1];
6 int dayIndex = 0;
7 for (int i = 0; i <= n; i++) dp[i] = 0;
8 for (int i = 1; i <= n; i++) {
9 if (i != days[dayIndex]) {
10 dp[i] = dp[i - 1];
11 } else {
12 int oneDayPass = dp[i - 1] + costs[0];
13 int sevenDayPass = dp[(i - 7 >= 0) ? i - 7 : 0] + costs[1];
14 int thirtyDayPass = dp[(i - 30 >= 0) ? i - 30 : 0] + costs[2];
15 dp[i] = oneDayPass < sevenDayPass ? oneDayPass : sevenDayPass;
16 dp[i] = dp[i] < thirtyDayPass ? dp[i] : thirtyDayPass;
17 dayIndex++;
18 }
19 }
20 return dp[n];
21}
22
23int main() {
24 int days[] = {1, 4, 6, 7, 8, 20};
25 int costs[] = {2, 7, 15};
26 int result = mincostTickets(days, 6, costs, 3);
27 printf("The minimum cost to travel is %d\n", result);
28 return 0;
29}The C code initializes a dynamic programming (DP) array where each index represents the cost to travel up to that day. For each given travel day, it computes the minimum cost considering each type of pass (1-day, 7-day, 30-day) and stores the result in the DP array.
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#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
class Solution {
int memo[366];
public:
int dfs(vector<int>& days, vector<int>& costs, int i) {
if (i >= days.size()) return 0;
if (memo[i] != -1) return memo[i];
int oneDay = costs[0] + dfs(days, costs, i + 1);
int j;
for (j = i; j < days.size() && days[j] < days[i] + 7; j++);
int sevenDay = costs[1] + dfs(days, costs, j);
for (j = i; j < days.size() && days[j] < days[i] + 30; j++);
int thirtyDay = costs[2] + dfs(days, costs, j);
return memo[i] = min(oneDay, min(sevenDay, thirtyDay));
}
int mincostTickets(vector<int>& days, vector<int>& costs) {
memset(memo, -1, sizeof(memo));
return dfs(days, costs, 0);
}
};This C++ implementation adopts a recursive strategy with memoization, similar to the C solution, by maintaining a memo array to eliminate repeated work. At each recursive call, it determines the cost of the travel pass combinations starting at the current day index.