Minimum Cost For Tickets | LeetCode 983 | C++, Java, Python

[@acceleratorlevel645]

this is the best solution to this problem ive seen so far!

[@KnowledgeCenter]

Thanks.

[@sahilanower9189]

There's a reason that KZbin recommendations are no doubt the best! 👌🔥

[@KnowledgeCenter]

Thanks.

[@aminurrahaman3186]

Ki re vai ..same jaigai ese porlam to

[@Jess-xx9ul]

Your videos have helped someone like me (coding noob) so much, thank you for the clear explanations everyday!

[@janmichaelaustria620]

seconded! your guidance has taken from zero to hero (well a little bit more than zero :))

[@oussamamoussaoui7131]

we can take the advantage that the array is sorted and use lower_bound() (which is O(log(n))), instead of a loop, (O(n)) to get the index of day7/day30: something like: d7 = lower_bound(days.begin() + i, days.end(), days[i] + 7) - days.begin();

[@ankoor]

Python: Similar Bottom-up Approach (solving from left to right) def mincostTickets(days, costs): n = len(days) T = [float('inf')] * n T[0] = min(costs) for i in range(1, n): w = i m = i while w >= 0 and days[i] - 7 < days[w]: w -= 1 while m >= 0 and days[i] - 30 < days[m]: m -= 1 T[i] = min(costs[0] + T[i-1], min(costs[1] + T[w], costs[2] + T[m])) return T[n-1]

[@LuckyCatTom]

FYI: It's incorrect, you can check it on the leetcode

[@siddharthsingh4330]

last_day = days[-1] dp = [0 for _ in range(last_day + 1)] days = set(days) for i in range(1, last_day + 1): if i in days: one = costs[0] + dp[i - 1] seven = costs[1] + dp[max(i - 7, 0)] thirty = costs[2] + dp[max(i - 30, 0)] dp[i] = min(one, seven, thirty) else: dp[i] = dp[i - 1] return dp[-1]

[@jimwoodward7293]

The DP strategy you used is very interesting. Are there any resources you can recommend to learn more about programming the bottom up approach? Preferably in Python. Thanks -- enjoy your videos.

[@nands4410]

Why do you prefer bottom up? Can you elaborate a bit more, Whenever I see overlapping subproblems I can only think of top down

[@KnowledgeCenter]

I like to think about smallest problem solve it, i.e., base case. Then like to make progress. Then think of generic case (i, ..) and what do I need to find optimal solution for this state in terms of smaller values. So, conceptually this is same as finding recursive relationship of higher i,j...etc in terms of smaller values.

[@JardaniJovonovich192]

In Top down approach apart from extra table space of O(n), we would even require additional space for recursion stack. In Bottom up approach we do not require that extra space for recursion stack.

[@satyaprakashyadav2388]

I watch your videos almost everyday. Thanks for making such insightful explanations. I want to know one thing from you : Which accessories do you use to create these videos. Please answer in detail. Loads of love to you for your amazing content.

[@satyaprakashyadav2388]

Can You please reply to this. I'll be very grateful to you sir. Simply tell me about the pen you use , which board,mike and recording etc.

[@rmadhavmca1]

I think if you add the days into Hashset, might avoid the while loop.

[@WKogut]

you should have used more descriptive variable names

[@BeatrizOliveira-yx4di]

Why are you assigning the elements in your vector to 365*costs[0]? For me it works just fine assigning them to 0

[@KnowledgeCenter]

You are right, we never used those values apart from (n+1)th value i.e., dp[n] = 0 . We assigned 3 values to dp[i] corresponding to day, week, and month and picked min() from there. I was earlier thinking to pick min of initial value with new ones. Ignore that initialization.