Dynamic Programming Playlist: kzread.info/dash/bejne/aWemla2Qmajcqc4.html

@insideout3795

Жыл бұрын

modified the solution to inplace class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: if not triangle: return 0 for row in range(len(triangle)-2, -1, -1): for index, value in enumerate(triangle[row]): triangle[row][index] = value + min(triangle[row+1][index], triangle[row+1][index+1]) return triangle[0][0]

I lost the hope when I realized my IQ was -90.

*THE* clearest way I've seen on this problem! Really appreciate the drawing at the end on how the algorithms stores the result. Thank you so much!!

As someone who has absolutely NO coding background and just started at mid-to-late August, I just want to THANK YOU for making these terrific videos! I just passed the first round of tech interview at Huawei only because of you!!! I highly recommend your channel to everyone who wants to become a swe!!!

Thanks for the video. I've been following along. 14:10 should be 3+4 = 7 I think.

@DoJoStan

3 жыл бұрын

It actually should be 10. [4, 1, 8, 3, 0] [7, 6, 10] [9, 10] [11]

@larrygoldstein2438

3 жыл бұрын

@@DoJoStan Why should it be 10 instead of 7? Thanks

@DoJoStan

3 жыл бұрын

​@@larrygoldstein2438 Sorry I got mistaken with what's on leetcode and whats the example that Neetcode has here in his video. It is actually 7 in his example. however on leetcode, the example given is [[2],[3,4],[6,5,7],[4,1,8,3]]. Which is 10. In the example that Neetcode has here he is evaluating [[2],[3,4],[6,5,4],[4,1,8,3]]

@omkarbhale442

10 ай бұрын

Right

This channel is a legitimate goldmine. I solved this problem top-down but I'm grateful I checked out this channel all the same because the bottom-up solution is 10x more elegant.

I did something clever and instead of allocating new memory I just reused the given array, starting from second last row to the top

@NeetCode

3 жыл бұрын

That's smart, I didn't think of that, nice!

I finally understood dynamic programming. Whoever fully understands the concepts in this video, will definitely pass the algorithm interview.

@SK-cd9kk

2 жыл бұрын

me understanding the theory but being too dumb for programming by myself

@yilmazbingol4838

2 жыл бұрын

@@SK-cd9kk you need practice. Do not give up so quick. How do you think people get good at something?

@SK-cd9kk

2 жыл бұрын

@@yilmazbingol4838 i am just at the beginning of learning solving algorithms, so i will go on

@AwesomeCadecraft

7 ай бұрын

Same! It feels so cool to finally understand the concepts, good luck on your programming journeys everyone

@14:13, dp row should be 7, 6, 7, right? 4+ min(8, 3) = 7

@inFamous16

2 жыл бұрын

It should be 7 in given example but in leetcode, there is 7 instead of 4. So, it should be 10 i.e., 7 + min(8, 3) = 10

@za168

Жыл бұрын

@@inFamous16 Thanks, I was so confused !

Best explanation on KZread, you make it seem so easy, thank you! :)

The solution just blew my mind. This approach is simply genius ! Thank You.

You are the best, you always make problems easier than they really are. Kudos!!!!!

Brilliant Explanation ! Please keep making more videos like this . Thanks

Thank you for such a clear explanation!

Such an intuitive solution! Thanks!

wonderful!! Excellent preparation for SW dev interview!!

@neetcode knows how to teach ds algo in the correct way... kudos to you

best explanation ever! Thank you

This solution is genius! Nice work.

Excellent visualization and explanation of your problems. Your voice is best suited for professor of any big university. Just one question - What tool do you use for visualization?

I did it myself, but thanks to NeetCode, I had no coding background, no degree, its been 4 months Ive started coding in Leetcode and unity ( a game engine ). I learned a lot in this channel.

@moulee007

Жыл бұрын

your leetcode id?

@hhcdghjjgsdrt235

Жыл бұрын

@@moulee007 Pramit Samanta user5010fN Ive just started and Im a civil engineer

Your visuals are unparalleled !!

I love your channel, and your videos

I dont think anyone can draw and explain recursive or dfs trees better than you. Thanks @neetcode. I added this question to 'Favorites' on my leetcode.

You are a legend indeed!!!!!!!

Can you just start out with dp[] = last row and iterate from the second to last row up to the first?

After your explanation , this problem is butter

謝謝！

the question is quite similar to minimum path sum in grid..... so here is the soln : class Solution { public: int minimumTotal(vector& triangle) { vector dp(201, vector(201, -1)); int result = solve(triangle, triangle.size(), 0, 0, dp); return result; } int solve(vector& triangle, int m, int i , int j , vector& dp){ int n = triangle[i].size(); if(i >= m && j >= n) return INT_MAX; if(i == m-1) return triangle[i][j]; if(dp[i][j] != -1) return dp[i][j]; int ans1 = solve(triangle, m, i+1, j, dp); int ans2 = solve(triangle, m, i+1, j+1, dp); int res = min(ans1, ans2) + triangle[i][j]; return dp[i][j] = res; } };

thank you that really helps

@NeetCode

2 жыл бұрын

Glad it helped!

You are the best

After 1 hour and a half of grinding, i solved it with a "Runtime: 88 ms, faster than 44.09% of Python3 online submissions for Triangle."(with dfs and memoization), i wouldn't have found it in an interview setting in a million years xD These pbs are tough...

This might be my favorite DP problem

@NeetCode

2 жыл бұрын

I definitely think it's underrated!

I am new at dp, I somehow manage to write the code but have trouble with memoization, can anyone help with this code? def total(i, row, count): if i>=len(triangle[row]): return float("inf") count+=triangle[row][i] if row==len(triangle)-1: return count return min(total(i, row+1, count), total(i+1, row+1, count)) return min(total(0, 1, count), total(1,1,count))

one can do O(1) space if use triangle matrix itself for DP matrix. no need for a bigger DP: we can just start from one-to-last row and move up

I think just to optimize space, you don't have to create a new array, you can replace the existing array provided.

why from the bottom to the top? why not from the top to bottom? thx~

why the time complexity is O(n) not O(n^2)?

I am always able to draw the decision tree for DP/recursive problems but am never able to convert it to code executable logic!!

@techbarikcom

2 жыл бұрын

You should practice more on implementation

@varunshrivastava2706

2 жыл бұрын

@@techbarikcom yeah man you are right

dp[i] = n + min(dp[i], dp[i+1]) is neet! After updating dp[0], we don't need its value for the rest of updates till we are done with the current row. This is due to the shape of a triangle. Update: You explained it already after the code :)

Can you comment a little on the input size?

awesome

So, I have IQ of more than 90, yay! In my opinion, this problem is the easiest of all medium Dynamic Programming problems on LC.

Can someone tell me when tu enumerate and when not to?

@zactamzhermin1434

2 жыл бұрын

Both works. Enumerating is just a shorter way to write code so you can: 1. Avoid writing range(len(array)) 2. Avoid writing array[idx] to get the item at the current `idx` index If you are not comfortable with enumerate yet just avoid it for now and use in range len. It does the exact same thing. ```python # slightly shorter enumerate code for idx, num in enumerate(array): ... # this is equivalent to above for loop for idx in range(len(array)): num = array[idx] ... ```

Time complexity is O(n)

I solved this problem before looking at this video so I'm glad my IQ of >= 90 is confirmed.

C++ solution for the same question class Solution { public: int minimumTotal(vector& nums) { int n = nums.size(); int last = nums[n-1].size(); int ans=nums[0][0]; vectordp(last+1,0); for(int i=n-1;i>=0;i--){ for(int j=0;j

class Solution { public: int minimumTotal(vector& triangle) { int n = triangle.size(); for(int i=n-2; i>=0; i--){ int m = triangle[i].size(); for(int j=0; j initially we have considered last row as leafs it-0: trriangle[3] = [4, 1, 8, 3] Now, start traversing triangle from 2nd last row to the top: it-1: triangle[2] = [7, 6, 10] it-2: triangle[1] = [9, 10] it-3: triangle[0] = [11] // final iteration storing our result at triangle[0] */

You made a mistake when explaining your intuition at 14:09, when you replaced 8 with 12, but should have been 7 i.e. (4 + min(8, 3)). Not something big but just telling FYI. Thanks for all the content

@tiyaaaa3917

Жыл бұрын

you are right

@sharad_dutta

Жыл бұрын

@@tiyaaaa3917 haha

LOoks like I have IQ less than 90.

WOW 🤩 now I am feeling like I have 130 IQ 😎

my IQ definitely below the 90

INPLACE SOLUTION, YOU CAN CHOOSE NOT TO USE THE EXTRA TABLE IF WANT TO. THANK YOU. ``` class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: if not triangle: return 0 for row in range(len(triangle)-2, -1, -1): for index, value in enumerate(triangle[row]): triangle[row][index] = value + min(triangle[row+1][index], triangle[row+1][index+1]) return triangle[0][0] ```

Great video, nice clickbait haha How did you learn data structures and algorithms?

Just a word of advice, not include dynamic programming in the title or hash tag, it's kind of a spoiler for many viewers who are attempting to solve the question first before watching your videos.

me watching this knowing that I have an IQ of float("-inf")

If someone(like me) wants to start from 1 row and go all the way to the last: def min_path_sum(triangle): dp = [float('inf')] * len(triangle[-1]) dp[0] = triangle[0][0] for row in triangle[1:]: for index, element in reversed(list(enumerate(row))): if index != 0: dp[index] = element + min(dp[index], dp[index-1]) else: dp[index] = element + dp[0] return min(dp)

This sounds like a tree with extra steps

Hahaha i have an iq of 136 ;) can solve this lolz

my iq 😥