Unique Paths - Leetcode 62 - Dynamic Programming (Python)

Master Data Structures & Algorithms for FREE at AlgoMap.io/
Code solutions in Python, Java, C++ and JS for this can be found at my GitHub repo here: github.com/gahogg/Leetcode-So...
Complete DSA Pathway Zero to Hero: • Data Structures & Algo...
Please check my playlists for free DSA problem solutions:
• Fundamental DSA Theory
• Array & String Questions
• 2 Pointers Questions
• Sliding Window Questions
• Binary Search Questions
• Stack Questions
• Linked List Questions
• Tree Questions
• Heap Questions
• Recursive Backtracking...
• Graph Questions
• Dynamic Programming (D...
My Data Science & ML CZcams Playlist: • Greg's Path to Become ...
Learn Python and Data Science FASTER at mlnow.ai :)
Support the content: / @greghogg
Follow me on Instagram: / greghogg5
Connect with me on LinkedIn: / greghogg
Follow me on TikTok: / greghogg5
Coursera Plus: imp.i384100.net/P0E3J6
My Favorite Courses:
Data Structures & Algorithms:
- UCalifornia San Diego DSA: imp.i384100.net/LP31oV
- Stanford Algorithms: imp.i384100.net/vNBoxd
- Python Data Structures: imp.i384100.net/NkZn47
- Meta Coding Interview Prep: imp.i384100.net/Y96rBJ
Python:
- UMichigan Python for Everybody: imp.i384100.net/QOLM73
- Python Mastery from MLNOW.ai: mlnow.ai/course-material/python/
- Google IT Automation w/ Python: imp.i384100.net/5g6Xyj
Web Dev / Full Stack:
- Meta Front-End Developer: imp.i384100.net/q4Jemy
- IBM Full Stack Developer: imp.i384100.net/Gj9dMn
- Meta Back-End Developer: imp.i384100.net/xkW0r5
- John Hopkins HTML, CSS & JS: imp.i384100.net/QyoRAA
- IBM DevOps: imp.i384100.net/kjd2r0
Cloud Development:
- AWS Fundamentals: imp.i384100.net/anqBjZ
- GCP Cloud Engineer: imp.i384100.net/g1jvqB
- Microsoft Azure Fundamentals: imp.i384100.net/EKm5O4
Game Development:
- Michigan State Unity Development: imp.i384100.net/6eOBnr
- UColorado C++ for Unreal Engine: www.coursera.org/specializati...
SQL & Data Science:
- SQL by MLNOW.ai: mlnow.ai/course-material/sql/
- Python for Data Science by MLNOW.ai: mlnow.ai/course-material/data...
- Google Data Analytics: imp.i384100.net/1rkWAR
- IBM Data Science: imp.i384100.net/P0ZRL6
- IBM Data Engineer: imp.i384100.net/4PbZyZ
Machine Learning & AI:
- ML Mastery at MLNOW.ai: mlnow.ai/course-material/ml/
- ML w/ Andrew Ng: www.coursera.org/specializati...
- Deep Learning w/ Andrew Ng: imp.i384100.net/a1kjJj

[@GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[@epicman9181]

There's actually a formula for this:
((m-1)+(n-1))!
-----------------------
(m-1)! * (n-1)!
This is because the problem can also be thought of as how many unique ways you can order the right and down movements.
In the 3x7 example, there are going to be 6 rightwards movements and 2 downwards movements (>>>>>>vv), creating an off by one error.
The rest of the formula is unique arrangements of characters with duplicates.

[@iyadahmed430]

awesome!

[@chandlerkenworthy3185]

I would argue using the same approach as in your video this code is a bit neater and easier to read
dp = [0] * n * m
for mi in range(0, m): # Number of rows
for ni in range(0, n): # Number of columns
i = (mi * n) + ni
if mi == 0 or ni == 0:
dp[i] = 1 # Sides of the grid are always 1s
continue
dp[i] = dp[i-1] + dp[i-n]
return dp[-1]

[@iyadahmed430]

My solution beats 100 percent of users runtime 😊
class Solution {
public:
int cache[100][100];
Solution() {
for (int i = 0; i < 100; i++)
for (int j = 0; j < 100; j++)
cache[i][j] = -1;
}
int uniquePaths(int m, int n) {
int &result = cache[m - 1][n - 1];
if (result != -1) return result;
if (m > 1 && n > 1) return (result = (uniquePaths(m, n - 1) + uniquePaths(m - 1, n)));
if (m > 1) return (result = uniquePaths(m - 1, n));
if (n > 1) return (result = uniquePaths(m, n - 1));
return (result = 1);
}
};