Triangle (LeetCode 120) | Easy tutorial | Bottom-up Top-down dynamic programming | StudyAlgorithms

This problem is helpful to understand how dynamic programming actually works. Given a triangle of integers, we need to find the minimum sum possible starting from the top most element. The problem follows an optimal sub-structure property and can be solved using either the top-down approach or the bottom-up approach using memoization. Watch the video to see animations and an easy explanation to understand how to approach such problems
Chapters:
00:00 - Intro
00:44 - Problem statement and description
03:16 - Why greedy algorithm will not work?
06:38 - Top-down dynamic programming
09:59 - Bottom-up dynamic programming
12:29 - Dry-run of Code
14:57 - Final Thoughts
📚 Links to topics I talk about in the video:
Brute Force Algorithms: • Brute Force algorithms...
Greedy Algorithmic Paradigm: • Greedy Algorithms with...
Dynamic Programming: • Dynamic Programming ea...
Other LeetCode solutions: • Leetcode Solutions
📘 A text based explanation is available at: studyalgorithms.com
Code on Github: github.com/nikoo28/java-solut...
Test-cases on Github: github.com/nikoo28/java-solut...
📖 Reference Books:
Starting Learn to Code: amzn.to/36pU0JO
Favorite book to understand algorithms: amzn.to/39w3YLS
Favorite book for data structures: amzn.to/3oAVBTk
Get started for interview preparation: amzn.to/39ysbkJ
🔗 To see more videos like this, you can show your support on: www.buymeacoffee.com/studyalg...
🎥 My Recording Gear:
Recording Light: amzn.to/3pAqh8O
Microphone: amzn.to/2MCX7qU
Recording Camera: amzn.to/3alg9Ky
Tablet to sketch and draw: amzn.to/3pM6Bi4
Surface Pen: amzn.to/3pv6tTs
Laptop to edit videos: amzn.to/2LYpMqn
💻 Get Social 💻
Follow on Facebook at: / studyalgos
Follow on Twitter at: / studyalgorithms
Follow on Tumblr at: / studyalgos
Subscribe to RSS feeds: studyalgorithms.com/feed/
Join fan mail: eepurl.com/g9Dadv
#leetcode #dynamicprogramming #interview

[@andrejiskra3391]

I think you structured your video very very well and explained the concepts and solutions perfectly. Timestamps were also very helpful. Thank you for creating this.

[@nikoo28]

glad you feel that way

[@manojtate9604]

Your explanation was top-notch !

[@kunalkheeva]

Appreciate your work! Most underrated channel though! Keep posting.

[@nikoo28]

fingers crossed :)

[@ganeshpatel3985]

love the way you teach

[@unemployedcse3514]

one vedio explains gist of dynamic programming and other concepts , thank you 😍

[@AkashYadav-di6kd]

Thank you very much, bhaiya.

[@mohammedilyas8824]

Great explanation sir,pls bring on some most tricky interview questions frequently asked

[@nikoo28]

Sure…i am adding new problems every week :)

[@vivekkumaryadav9862]

the way that u explain with example it help a lot to understand
thanks sir

[@nikoo28]

that is so nice of you

[@leetcodebaby6680]

When you were explaining the problem, you left explaining after 2 rows when things really started becoming tricky. You left at the point when it was most needed.

[@nikoo28]

I discuss 2 approaches in the solution, a top-down and a bottom-up approach. Does that help?
Can you tell me the timestamp at which you struggled? I can help more.

[@vivekkumaryadav9862]

TC -> O(n^2)
S.C -> O(n^2)

[@032_RishavDey]

Sir we can optimise the Space Complexity to O(N)

[@nikoo28]

what will your approach be?

[@032_RishavDey]

@@nikoo28 just have one dp array of size equal to N, and initialise it with values in last row. Then perform bottom up approach. So our answer is in dp of 0.

[@nikoo28]

@@032_RishavDey that is indeed smart.. 😄