# 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[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 * 10^9$.

### Combinatorics

```
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

```
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

```
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

```
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 |

## 03 July |

## 04 July |

## 05 July |

## 06 July |

## 07 July |

## 08 July |

## 09 July |

## 10 July |

## 11 July |

## 12 July |

## 13 July |

## 14 July |

## 15 July |

## 16 July |

## 17 July |

## 18 July |

## 19 July |

## 20 July |

## 21 July |

## 22 July |

## 23 July |

## 24 July |

## 25 July |

## 26 July |

## 27 July |

## 28 July |

## 29 July |

## 30 July |