Minimum Cost for Tickets - Dynamic Programming - Leetcode 983 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: neetcode1
🥷 Discord: discord.gg/ddjKRXPqtk
🐮 Support the channel: www.patreon.com/NEETcode
⭐ BLIND-75 PLAYLIST: kzbin.info/www/bejne/gX3PiXZ8fJqHpKM
💡 CODING SOLUTIONS: kzbin.info/aero/PLot-Xpze53leF0FeHz2X0aG3zd0mr1AW_
💡 DYNAMIC PROGRAMMING PLAYLIST: kzbin.info/www/bejne/bWTVZH6Nnqqpr80
🌲 TREE PLAYLIST: kzbin.info/www/bejne/hZ-2n2WOerZng7s
💡 GRAPH PLAYLIST: kzbin.info/www/bejne/e5isZqGLbsqnpLc
💡 BACKTRACKING PLAYLIST: kzbin.info/www/bejne/ppfMgpKGiJaabqc
💡 LINKED LIST PLAYLIST: kzbin.info/www/bejne/fWHCemCQe5WGaZo
💡 BINARY SEARCH PLAYLIST: kzbin.info/aero/PLot-Xpze53leNZQd0iINpD-MAhMOMzWvO
📚 STACK PLAYLIST: kzbin.info/aero/PLot-Xpze53lfxD6l5pAGvCD4nPvWKU8Qo
Problem Link: leetcode.com/problems/minimum-cost-for-tickets/
0:00 - Read the problem
3:45 - Drawing Explanation
12:24 - Coding Explanation
leetcode 983
This question was identified as an interview question from here: github.com/xizhengszhang/Leetcode_company_frequency
#dynamic #programming #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@NeetCode]

💡 DYNAMIC PROGRAMMING PLAYLIST: kzbin.info/www/bejne/bWTVZH6Nnqqpr80

[@dollyvishwakarma2]

Amazing explanation overall. Just that tbh this was the first video of yours(trust me I have watched so many) that I had to re-watch to understand. I think this was a tricky question. Kudos to the good work !

[@annonymous.]

I wonder. I can't implement my thought easily, but you make complex problems easy to understand and write in such a simple way! Hats off to you!

[@jlecampana]

Thank you for showing a clear explanation for the Top Down approach, most of the other videos for this problem go straight to bottom-up, and that approach is less intuitive.

[@tianjoyce7940]

for the third case, why can u assume that on day i, the customer can for sure buy a ticket?

[@hemankundu]

Grateful for the series!

[@ningzedai9052]

I come up an solution which is O(365) time complexity. but not sure if O(365) can be considered as O(1) class Solution: def mincostTickets(self, days: List[int], costs: List[int]) -> int: dp = [0] * 366 curr = 0 for i in range(1, 366): if curr < len(days) and i == days[curr]: curr += 1 res1 = dp[i - 1] + costs[0] res2 = 0 if i - 7 < 0 else dp[i - 7] res2 += costs[1] res3 = 0 if i - 30 < 0 else dp[i - 30] res3 += costs[2] dp[i] = min(res1, res2, res3) else: dp[i] = dp[i - 1] return dp[-1]

[@dead4sure]

i thought of something similar too but this kinda solution is disregarded due to its additional storage requirements

[@DavidDLee]

Yes, it should work as long as the year is really 365 days long or shorter. For a "year" which is longer, it will not. Of course, if N is

[@ash4733]

Hi, @NeetCode is it possible to implement and show the burtforce approach the one you explained in the beginning that would be the great help pls. Thank you for your videos and it's helping me a lot. Appreciated with your hard work

[@saikankanala9690]

class Solution: def mincostTickets(self, days: List[int], cost: List[int]) -> int: n = len(days) def helper(i,day): if i >= n: return 0 ans = sys.maxsize if days[i] > day: ans = min(ans,cost[0]+helper(i+1,days[i])) ans = min(ans,cost[1]+helper(i+1,days[i]+6)) ans = min(ans,cost[2]+helper(i+1,days[i]+29)) else: ans = min(ans,helper(i+1,day)) return ans a = helper(0,0) return a

[@ash4733]

@@saikankanala9690 awesome. thanks

[@VarunMittal-viralmutant]

@@saikankanala9690 Thanks for this. I implemented it the same but that errors with TLE on LeetCode. I could not figure out how to implement memoization in this one. Did u do that ? The simple dp[i] doesn't work, right ?

[@CSBAjay]

@@VarunMittal-viralmutant class Solution: def mincostTickets(self, days: List[int], costs: List[int]) -> int: n = len(days) dp = {} def helper(i,day): if i >= n: return 0 if (i,day) in dp: return dp[(i,day)] ans = float('inf') if days[i] > day: ans = min(ans,costs[0]+helper(i+1,days[i])) ans = min(ans,costs[1]+helper(i+1,days[i]+6)) ans = min(ans,costs[2]+helper(i+1,days[i]+29)) else: ans = min(ans,helper(i+1,day)) dp[(i,day)] = ans return ans a = helper(0,0) return a

[@harishsn4866]

Hey, this bottom-up solution isn't working. Maybe because we are returning dp[0] in the end? it shows key error. I changed it to dp[i] but it gives wrong output. Please it would be grateful if you could clarify it.

[@hongliangfei3170]

Thanks for the video. One suggestion, you can do a binary search on the "days" array given the next start date since days is sorted.

[@DavidDLee]

You could, but: (1) it will not improve the runtime complexity since O(30) is O(1) (2) More complex code in an interview is a risk for errors

[@rock23754]

best explanation I could ever find. Thanks

[@Tough802Peter]

What a real chad in coding world!

[@cokeoutube]

@neetcode great video thanks!. I got a question, why doesn't the while loop inside the recursion affect the time complexity?

[@abhishekpawar8458]

it's constant size array.

[@emeksthecreator]

it runs in constant time

[@JohnIdlewood]

Good algorithm ! But how to prove that it's optimal ? For instance (wrong example, but still good for an argument), I can argue that sometimes buying tickets in advance can lead to a more optimal solution.

[@lukealberts.hastings]

That would be impossible since the prices will always not change. Let's assume that there were a most optimal solution which involves at least one in-advance purchase which can not be replaced by a purchase made on a travelling day. Since it is a solution to this problem, it must cover all the days when we will travel. For every "in-advance" purchase, if we choose to do it on the next closest travelling day when we will travel, every travelling day the "in-advance" purchase can cover will also be covered by the purchase made on the next closest travelling day with the same expense. Since there are no limitations on the amount of tickets we are allowed to purchase within a single day, it's safe to say that every optimal "in-advanced" purchase can be replaced by an alternative which is made on a travelling day. Therefore, all possible optimal solutions to this problem can be expressed by a combination only consisting of purchases made on a travelling day

[@gokulakv]

Great explanation with decision tree

[@Philgob]

beautiful explanation

[@gayathribs5309]

Java solution for the same: public int mincostTickets(int[] days, int[] costs) { return dfs(0, days, costs, new HashMap()); } public int dfs(int i, int[] days, int[] costs, HashMap dp) { if (i == days.length) { return 0; } if (dp.containsKey(i)) { return dp.get(i); } int[] dayRow = new int[]{1, 7, 30}; for (int d = 0; d < 3; d++) { int j = i; while (j < days.length && days[j] < days[i] + dayRow[d]) { j += 1; } int val = Math.min(dp.getOrDefault(i, Integer.MAX_VALUE), costs[d] + dfs(j, days, costs, dp)); dp.put(i, val); } return dp.get(i); }

[@janvidalal476]

Love the picture form ⚡👁

[@rdwok14]

Can someone explain line 8 if i in dp: return dp[i]? I thought i is an index and dp contains the cache of costs so i would never be in dp unless a cost happened to equal an index. Edit: nevermind, I get it. dp is a dictionary and the keys are i. dp[i] is the cost of getting to the day given by index i.

[@Kumar-rp2dk]

Also in few cases minimum is related to binary search also

[@VarunMittal-viralmutant]

Can someone please share the code for tabulation DP going from index 0 to the end ? Will that be O(N^2) b'coz for each index one has to look at all the previous indices ?

[@bryanlozano8905]

There is an O(N^2) solution similar to LIS, but given my lower metric on LC it is not optimal.

[@VarunMittal-viralmutant]

@@bryanlozano8905 Actually I found a solution on LeetCode which I really liked def min_ticket_cost(days, costs): """ We create a complete dp table for all days, starting from 0 to last day of travel Each day we keep track of how much did we spend till that day Since we don't travel on certain days, there is no spending, so we simply copy the expenses from previous day Other day, we take min of current day expense plus current day - {1, 7 or 30} days """ # dp[0] is 0 when there is no day to travel, 0 expense dp = [0 for _ in range(days[-1] + 1)] dy = set(days) for i in range(1, days[-1] + 1): if i not in dy: dp[i] = dp[i - 1] else: # max(0, i-x) this makes sure that we don't go below 0 dp[i] = min(dp[max(0, i - 1)] + costs[0], # 1 day pass dp[max(0, i - 7)] + costs[1], # Weekly pass dp[max(0, i - 30)] + costs[2]) # Monthly pass return dp[-1]

[@yugash4474]

my DP solution without recursion class Solution: def mincostTickets(self, days: List[int], costs: List[int]) -> int: dp = [min(costs)] for i in range(1, len(days)): seven = bisect.bisect_left(days, days[i]-6) thirty = bisect.bisect_left(days, days[i]-29) val = dp[-1]+costs[0] if seven

[@pratikkumar7293]

upper bound works for getting next day

[@xavier.antony]

In my view, the time complexity for any algorithm to solve this problem is O(1). Basically we should not even consider analyzing it in Big O. BTW: You guys are doing a fantastic job of publishing leetcode problem videos.

[@pedrov8868]

What if the problem specs were different and the environment was constrained? If it really is just an excercise there's still value in the analysis.

[@YT.Nikolay]

All dp problems are too difficult for me 😭😭😭😭

[@subashsakthivels8808]

go watvh striver dp series , then come here

[@martinemanuel8239]

Awesome video ! , but I have a question at min 08:20 why one ticket of $2 brings me to 20, if I stay in 8 ??? must be 10 a I think

[@DavidDLee]

You paid on day 1 for a 7-day pass, which covers all days 1 through 7. Then, you chose to pay for a single day pass to cover day 8. Now, the next day you need to travel is day 20. You don't need to travel in any day between day 8 and day 20. So, you choose to pay for another single-day pass for day 20.

[@4400marko]

dp is a map, but what does the name stand for? Like dp is the abbreviation of...?

[@liuhh02]

dp is the abbreviation of "dynamic programming"

[@daniyarabc]

Great video, thanks!

[@shaon6996]

Great explanation!

[@saniyaambavanekar1431]

can you explain odd even jump question from leetcode?

[@SHUBHAMRAGHUWANSHI_ASKN]

Simple Java DP: int N = days.length, index = 0, lastDay = days[days.length - 1]; DP[0] = 0; for (int i = 1; i = 7 ? DP[i - 7] : 0) + costs[1]; int c3 = (i >= 30 ? DP[i - 30] : 0) + costs[2]; DP[i] = Math.min(c1, Math.min(c2, c3)); index++; } else { DP[i] = DP[i - 1]; } } return DP[lastDay];

[@OIAOa]

thank you sir

[@AryanSingh-zv5ch]

Thnx man 🥺

[@dataman4503]

Well this is Memoization approach. In interviews, I believe that if a DP approach is available, interviewers look for that approach.

[@電腦騙徒剋星]

memoization is literally dp, if you get the dp there is no way you can't do the tabular approach , lmfao

[@Isha_Sethi]

You really don't know how to explain 😑

[@NeetCode]

nobody's perfect =)

[@Isha_Sethi]

@@NeetCode if you are putting the time and effort in making videos...why not try to become more of a teacher than a programmer so that your videos may be helpful to a larger crowd 🤷

[@Flyfishing9898]

@@Isha_Sethi Maybe you're just bad 🤷

[@yodude8325]

I dont understand how can you say that, I almost everytime watch his videos when I can't come up with a solution. Neetcode you are totally perfect to explain problems!!

[@tonero5651]

@@NeetCode Dude You're explanations are way too good man. Keep up the good work