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

0:00 - Read the problem
3:45 - Drawing Explanation
12:24 - Coding Explanation

leetcode 983

#dynamic #programming #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[dollyvishwakarma]

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!

[AdventurousAnomaly]

A slightly different way to implement the dp array, which i feel is easier to understand.

def mincostTickets(self, days: List[int], costs: List[int]) -> int:


costdp = [0]

#these are indexes
d_1elem = 0
d_7elem = 0
d_30elem= 0

currentElem = 1

for x in days:

#based on x change all the d_ values
while(x-days[d_1elem]>=1):
d_1elem += 1

while(x-days[d_7elem]>=7):
d_7elem += 1

while(x-days[d_30elem]>=30):
d_30elem += 1



costOfd_1 = costs[0]+costdp[d_1elem]
costOfd_7 = costs[1]+costdp[d_7elem]
costOfd_30 = costs[2]+costdp[d_30elem]

costdp.append(min(costOfd_1, costOfd_7, costOfd_30))
currentElem += 1

return costdp[currentElem-1]

[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.

[dheepthaaanand]

dp stores the min cost to travel from day of the ith index till the day of the last index. Hence it is only dependent on future days, and the final result is dp[0]

c is the cost for covering all days within d. Once it exceeds d, we break, and calculate cost from the index we broke at i.e j

[tianjoyce]

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

[hongliangfei]

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.

[ash]

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

[ningzedai]

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]

[rock]

best explanation I could ever find. Thanks

[pratikkumar]

upper bound works for getting next day

[Kumar-rpdk]

Also in few cases minimum is related to binary search also

[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.

[YT.Nikolay]

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

[gayathribs]

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<Integer, Integer> 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);
}

[Abhisheksharma-evd]

Is dp accessible inside the dfs function?

[yugash]

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<=0:
val = min(val, costs[1])
else:
val = min(val, dp[seven-1]+costs[1])
if thirty<=0:
val = min(val, costs[2])
else:
val = min(val, dp[thirty-1]+costs[2])
dp.append(val)
return dp[len(days)-1]

[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.

[harishsn]

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.

[cokeoutube]

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