August | 2022 | Leetcoding Challenge
Post
Cancel

# August | 2022 | Leetcoding Challenge

## 01 July | 62. Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., $grid$). 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 * 10^9$.

### Combinatorics

1 2 3 4 5 6 7 8 9 10 11 12 13 int uniquePaths(int m, int n) { int N = n+m-2; int r = min(n,m) - 1; double res = 1; for(int i=1; i<=r; ++i, N--) res = res * (N) / i; return (int)res; } 

### 2D Memoization

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 int solve(int i,int j,int m,int n,vector<vector<int>> &dp) { if(i>=m||j>=n) return 0; if(i==m-1&&j==n-1) return 1; if(dp[i][j]!=-1) return dp[i][j]; return dp[i][j]=solve(i+1,j,m,n,dp)+solve(i,j+1,m,n,dp); } int uniquePaths(int m, int n) { vector<vector<int>> dp(m,vector<int>(n,-1)); return solve(0,0,m,n,dp); } 

### 1D Memoization

1 2 3 4 5 6 7 8 9 int uniquePaths(int m, int n) { vector<int> cur(n, 1); for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { cur[j] += cur[j - 1]; } } return cur[n - 1]; } 

### Tabulation

1 2 3 4 5 6 7 8 int uniquePaths(int m, int n) { vector<vector<int>> dp(m, vector<int>(n, 1)); for (int i = 1; i < m; i++) for (int j = 1; j < n; j++) dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; return dp[m - 1][n - 1]; } 

## 02 July |

###

1 

## 03 July |

###

1 

## 04 July |

###

1 

## 05 July |

###

1 

## 06 July |

###

1 

## 07 July |

###

1 

## 08 July |

###

1 

## 09 July |

###

1 

## 10 July |

###

1 

## 11 July |

###

1 

## 12 July |

###

1 

## 13 July |

###

1 

## 14 July |

###

1 

## 15 July |

###

1 

## 16 July |

###

1 

## 17 July |

###

1 

## 18 July |

###

1 

## 19 July |

###

1 

## 20 July |

###

1 

## 21 July |

###

1 

## 22 July |

###

1 

## 23 July |

###

1 

## 24 July |

###

1 

## 25 July |

###

1 

## 26 July |

###

1 

## 27 July |

###

1 

## 28 July |

###

1 

## 29 July |

###

1 

## 30 July |

###

1