In the Leetcode Unique Paths problem solution There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m – 1][n – 1]). The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * 109.
Example 1:
Input: m = 3, n = 7
Output: 28
Example 2:
Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
- Right -> Down -> Down
- Down -> Down -> Right
- Down -> Right -> Down
Constraints:
- 1 <= m, n <= 100
Solution in C Programming
int uniquePaths_help(int **dp, int x, int y, int m, int n) {
if(x+1 >= m || y+1 >= n) return 1;
/* Search count from table */
if(dp[x][y]) return dp[x][y];
int k = 0;
// Go right
dp[x+1][y] = uniquePaths_help(dp, x+1, y, m, n);
k += dp[x+1][y];
// Go down
dp[x][y+1] = uniquePaths_help(dp, x, y+1, m, n);
k += dp[x][y+1];
return k;
}
int uniquePaths(int m, int n) {
/* start from (0, 0) to (m-1, n-1), only move right or down */
int **dp = malloc(m*sizeof(int *));
for(int i=0;i<m;i++) {
dp[i] = malloc(n*sizeof(int));
memset(dp[i], 0, n*sizeof(int));
}
dp[0][0] = uniquePaths_help(dp, 0, 0, m, n);
// for(int i=0;i<m;i++) {
// for(int j=0;j<n;j++) {
// printf("%4d,", dp[i][j]);
// }
// printf("\n");
// }
return dp[0][0];
}Solution in C++ Programming
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n,0));
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(i==0 && j==0){
dp[0][0] = 1;
}
else if(i-1<0 && j-1>=0){
dp[i][j] = dp[i][j-1];
}
else if(i-1>=0 && j-1<0){
dp[i][j] = dp[i-1][j];
}
else{
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
};
Solution in Java Programming
class Solution
{
public int uniquePaths(int m, int n)
{
int[] ans = new int[m];
Arrays.fill(ans, 1);
for(int i = 1; i < n; i++)
{
for(int j = 1; j < m; j++)
{
ans[j] = ans[j] + ans[j-1];
}
}
return ans[m-1];
}
}Solution in Python Programming
class Solution:
def uniquePaths(self, m, n):
# the base case is that if robot just go in the first column or the first row, there will be only one possible path for each, since the robot can only go down or right.
# that's why we intialize all values as 1, to represent the first row
record = [1]*n
# and we start from index 1 for row and column for the same sense.
for i in range(1,m):
for j in range(1,n):
record[j] = record[j-1]+record[j]
return record[-1]Solution in C# Programming
public class Solution {
public int UniquePaths(int m, int n) {
int[,] table = new int[m,n];
for(int i = m-1; i >= 0; i--){
for(int j = n -1; j >= 0; j--){
if(i == m -1 || j == n -1){
table[i, j] = 1;
}
else{
table[i,j] = table[i+1, j] + table[i, j+1];
}
}
}
return table[0,0];
}
}Also read,