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 !
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.
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
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
@@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 ?
@@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
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]
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.
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
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.
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.
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.
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 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]
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
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.
@@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 🤷
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!!
💡 DYNAMIC PROGRAMMING PLAYLIST: th-cam.com/video/73r3KWiEvyk/w-d-xo.html
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 !
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!
Grateful for the series!
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.
for the third case, why can u assume that on day i, the customer can for sure buy a ticket?
beautiful explanation
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
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
@@saikankanala9690 awesome. thanks
@@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 ?
@@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
What a real chad in coding world!
best explanation I could ever find. Thanks
Love the picture form ⚡👁
Great explanation with decision tree
All dp problems are too difficult for me 😭😭😭😭
go watvh striver dp series , then come here
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.
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
Great video, thanks!
Great explanation!
upper bound works for getting next day
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]
i thought of something similar too but this kinda solution is disregarded due to its additional storage requirements
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
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.
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
Also in few cases minimum is related to binary search also
@neetcode great video thanks!. I got a question, why doesn't the while loop inside the recursion affect the time complexity?
it's constant size array.
it runs in constant time
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.
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.
thank you sir
Thnx man 🥺
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.
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.
can you explain odd even jump question from leetcode?
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);
}
dp is a map, but what does the name stand for? Like dp is the abbreviation of...?
dp is the abbreviation of "dynamic programming"
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 ?
There is an O(N^2) solution similar to LIS, but given my lower metric on LC it is not optimal.
@@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]
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
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
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.
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];
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
You really don't know how to explain 😑
nobody's perfect =)
@@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 🤷
@@Isha_Sethi Maybe you're just bad 🤷
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!!
@@NeetCode Dude You're explanations are way too good man. Keep up the good work