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]
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!!!
@@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]]
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; } };
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 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.
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.
Top Down code for the idea described here, if anyone's interested :) class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: @cache def dfs(i, j): if i + 1 == len(triangle): return triangle[i][j] left = triangle[i][j] + dfs(i + 1, j) right = triangle[i][j] + dfs(i + 1, j + 1) return min(left, right) return dfs(0, 0)
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
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...
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 :)
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] */
Why not to store dp actually in triangle row itself? You gonna reduce unnecessar space usage, this my solution (JAVA): public int minimumTotal(List triangle) { for (int row = triangle.size()-2; row >= 0; row--){ List currRow = triangle.get(row); List prevRow = triangle.get(row+1); for ( int i = 0; i < currRow.size(); i++){ currRow.set(i, currRow.get(i) + Math.min(prevRow.get(i), prevRow.get(i+1))); } } return triangle.get(0).get(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
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] ```
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.
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))
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] ... ```
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)
