Triangle - Dynamic Programming made Easy - Leetcode 120

0:00 - Read the problem
1:15 - Drawing solution
11:00 - Coding solution

leetcode 120

#facebook #dynamicprogramming #python

[shrimpo]

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!!!

[heyrmi]

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

[gunabalang]

after 120 consecutive days of practicing, now i can solve problem just after seeing your visual explanation.

[ayushrawat]

the question is quite similar to minimum path sum in
so here is the soln :
class Solution {
public:
int triangle) {

vector<vector<int>> dp(201, vector<int>(201, -1));
int result = solve(triangle, triangle.size(), 0, 0, dp);
return result;
}

int solve(vector<vector<int>>& triangle, int m, int i, int j, vector<vector<int>>& 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;
}
};

[AIPlayerrrr]

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

[benjaminjorgensen]

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.

[shelllu]

*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!!

[thelookofdisapproval]

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

[yilmazbingol]

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

[ax]

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

[kartikhegde]

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

[helario]

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?

[hhcdghjjgsdrt]

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.

[shubhaverma]

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.

[ritwik]

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

[vijethkashyap]

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)

[m.m.farhad]

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

[nihshrey]

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

[horanj.]

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

[numberonep]

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