Minimum Difficulty of a Job Schedule - Leetcode 1335 - Python

[@walkastray007]

Hey Neetcode! I really appreciate the daily leetcode problem videos. They're such a nice way to start my day. It's sort of a ritual for me at this point to attempt a leetcode problem. I actually managed to get the correct thoughts/observations to solve the problem, but actually translating that into code was a bit tricky. As most hard problems are. Hope to see you tomorrow!

[@minaFbeshay]

The best to explain dynamic programming so far! Keep it bro

[@tusov8899]

Thanks for sharing! BTW, We can add the following condition in your dfs function to prune the useless states. remain_tasks = (n - 1) - i + 1 if remain_tasks < d: return math.inf

[@yang5843]

Was hoping you would come in clutch today to solve the problem!

[@nahidtanvir5901]

Shouldn't I calculate cur_max before checking cache?

[@aadil4236]

You are doing a really amazing and good work Navdeep. May god gives you everything you want in life. Happy New Year in advance my friend! You are a really amazing teacher! God bless you.

[@caleb.39]

Wow today's problem was so much easier than yesterday's lol. yesterday's I had spent 40 minutes trying to think about it before seeing your video. Today's problem I was able to solve it by myself in 20 minutes

[@venketeshpanda5183]

And our saviour is here :D

[@Manish-fd5jb]

Just put that DP check condition after calculating cur_max; it makes a big difference.

[@Philgob]

beautiful solution

[@laumatthew71]

Great explanation as usual, thank you sir !

[@mahimanzum]

The time complexity analysis is incorrect i believe. It should be O(n*d*max_value_of_array) max value of array and length of the array are different values. Please correct me if i am wrong

[@NeetCodeIO]

Yeah you're right, but I think it would be distinct_vals_in_array

[@yang5843]

@@NeetCodeIO isn't max value a constant

[@hamirmahal]

O(n*d*distinct_vals_in_array) is still O(n*d*n) because there are at most n distinct values in the array.

[@prajjwaldubey5787]

In the interview do I need to do the recursive + caching approach or the tabulation approach for any dp problem ????

[@tanmaychavan7004]

Thanks a bunch, was waiting for this.

[@AravindBadavath-u2u]

I am wondering if you can explain the monotonic stack solution as it helps learn everyone new concept. Thank you :)

[@SergeKnysh]

Great, all good now - thanks a lot

[@oijgg3p]

class Solution: def minDifficulty(self, jobDifficulty: List[int], d: int) -> int: n = len(jobDifficulty) if n < d: return -1 # Cannot schedule all jobs in d days memo = {} def dp(day, idx): if (day, idx) in memo: return memo[(day, idx)] if day == 1: # On the last day, we need to finish all remaining jobs, so return the maximum difficulty memo[(day, idx)] = max(jobDifficulty[idx:]) return memo[(day, idx)] min_difficulty = float('inf') max_difficulty = 0 # Iterate backward to find the minimum difficulty for i in range(idx, n - day + 1): max_difficulty = max(max_difficulty, jobDifficulty[i]) rest_difficulty = dp(day - 1, i + 1) min_difficulty = min(min_difficulty, max_difficulty + rest_difficulty) memo[(day, idx)] = min_difficulty return min_difficulty result = dp(d, 0) return result if result != float('inf') else -1

[@GameFlife]

fast fix tks NEET!

[@YashRekha594]

I consider myself very bad at dynamic programming. I need to start from the basic DP. Please suggest where I can start and learn DP.

[@sadiksikder7014]

climbing stairs, target sum, house robber, coin change, lcs

[@satwiktatikonda764]

if we give this memoization code in a interview will the interviewer be satisfied or will he ask us to optimize more and write a tabulation code?

[@6kostia]

you can get ~150ms for a recursive solution

[@7yu-y9f]

Great Explanation but why don't you solve this problem in bottom up approach!

[@caothanhluan1813]

I think memoization is kinda straightforward to solve this question

[@7yu-y9f]

@@caothanhluan1813 ya may be u are right ✅

[@yang5843]

class Solution { Map map = new HashMap(); public int minDifficulty(int[] jobDifficulty, int d) { if ( jobDifficulty.length < d ) return -1; return dfs(0,jobDifficulty,d,-1); } int dfs(int i, int[] jb, int d, int max) { if ( map.containsKey(i+" "+d+" "+max)) return map.get(i+" "+d+" "+max); if ( d == 0 && i == jb.length ) return 0; if ( d == 0 || i == jb.length ) return 10000; max = Math.max(max,jb[i]); //take int min = dfs(i+1,jb,d,max); //ignore min = Math.min(min,max + dfs(i+1,jb,d-1,-1)); map.put(i+" "+d+" "+max,min); return min; } }

[@chugisan6847]

Is making a map-key by concatenating values safe? I mean, for i = 23, d = 4, max = 5 and for i = 2, d = 34, max = 5, the map-key would be 2345 in both the cases. I know the chances for this to happen are very slim, but I just wanted to know if this way of making map-keys is standard or it's something that you use for yourself.

[@yang5843]

@@chugisan6847 good question, I'm space separating the integers so that doesn't happen

[@chugisan6847]

@@yang5843 Got you! Thank you for the answer.

[@joydeeprony89]

return 10000 , please share the logic behind magic number 10000 ?

[@yang5843]

@@joydeeprony89 it's an arbitrary large number, if I used max int here, there would be an overflow

[@shreehari2589]

God damn one heck of a problem this was

[@tariqelamin5847]

First comment

[@srirambharadwaj1937]

can anyone help me with this,..why this code doesn't work. as expected class Solution: def minDifficulty(self, jobDifficulty: List[int], d: int) -> int: n = len(jobDifficulty) if n

[@sadiksikder7014]

how are you returning todayCost when you have not define it

[@MP-ny3ep]

Beautiful explanation as always. Thank you.