Minimum Path Sum | Dynamic Programming (LeetCode)

Here is a step by step explanation of a dynamic programming problem called "Minimum Path Sum". This problem is primarily asked at Amazon, Google, and Goldman Sachs. In this problem, we must find the shortest path sum from the top left of our grid to the bottom right of our grid, but we can only move in the directions right or down. To solve this problem, we utilize dynamic programming, specifically a bottom-up approach where we start with a base case and work our way to the solution we need. We use a recurrence relation, essentially just a simple equation, to ensure we make use of previous calculations we have already computed. The recurrence relation used to solve this problem is the following: dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + dp[i][j] The time complexity of our solution is O(N * M) where N is the number of rows and M is the number of columns in our grid. Our space complexity is constant since we are utilizing our input to store the computed results; however, make sure you clarify with your interviewer whether you can use the input as storage! Check out my interview prep platform for learning the patterns! 📢 Interview Prep Platform: https://algoswithmichael.com 🎧 Join the community Discord: https://discord.gg/aVWsAaaCtT 💰 Support me on Patreon: https://www.patreon.com/michaelmuinos 🔗Follow me on LinkedIn: https://www.linkedin.com/in/michael-muinos 📂Follow me on Github: https://github.com/MichaelMuinos