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.
1function mincostTickets(days, costs) {
2 let lastDay = days[days.length - 1];
3 let dp = new Array(lastDay + 1).fill(0);
4 let dayIndex = new Set(days);
5 for (let i = 1; i <= lastDay; i++) {
6 if (!dayIndex.has(i)) {
7 dp[i] = dp[i - 1];
8 } else {
9 dp[i] = Math.min(
10 dp[i - 1] + costs[0],
11 (dp[i - 7] || 0) + costs[1],
12 (dp[i - 30] || 0) + costs[2]
13 );
14 }
15 }
16 return dp[lastDay];
17}
18
19console.log(mincostTickets([1,4,6,7,8,20], [2,7,15])); // Output: 11The JavaScript implementation follows a similar pattern to other dynamic programming solutions, tracking the minimum cost up to the last travel day. It uses, Map to quickly determine travel days and handles each travel day dynamically by checking the cost using 1, 7, or 30 day passes.
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
The JavaScript implementation employs a recursive function with memoization to derive the minimal ticket purchasing cost. By examining each potential combination of travel passes, the solution updates the memoization array to reflect the minimal incurred expenses.