2 minutes

# Leetcode-62

https://leetcode.com/problems/unique-paths/

**Explanation of solution**

**Explanation of solution**

Looking at this problem, we can recursively brute force all possible solutions by getting every single move we can make on the grid.

**First Solution: Brute Force Solution TLE**

```
func uniquePaths(m int, n int) int {
if m == 1 || n == 1{ return 1 }
return uniquePaths(m - 1, n) + uniquePaths(m, n - 1)
}
```

**Explanation of First Solution**

- Our base case is either when
`m == 1`

or`n == 1`

- If we have not hit our base case we add the recursive calls. We subtract from
`m`

making us move down and we subtract from`n`

to move right.

Since the first solution, Time Limit Exceed, we can implement memoization to store results from a specific position in the matrix.

**Second Solution: Memoized Solution**

```
func uniquePaths(m int, n int) int {
return pathFinder(m,n, map[[2]int]int{})
}
func pathFinder(m int, n int, dp map[[2]int]int) int {
var pos = [2]int{ m, n }
if (m == 1 || n == 1 ) || dp[pos] > 0 {
return dp[pos] + 1
}
dp[pos] = pathFinder(m - 1, n, dp) + pathFinder(m, n - 1, dp) - 1
return dp[pos] + 1
}
```

**Explanation of Second Solution**

- The variable
`pos`

is the key for the`dp`

map. - The if statment
`(m == 1 || n == 1 ) || dp[pos] > 0`

is for when either we have hit the base case of`m`

or`n`

equaling`1`

or`dp[pos] > 0`

meaning that we have already stored the result of`dp[pos]`

. `dp[pos] = pathFinder(m - 1, n, dp) + pathFinder(m, n - 1, dp) - 1`

is when we add the recursive calls of pathFinder, one of the calls being when we subtract from`m`

essentially moving down, and one of the calls being when we subtract from`n`

making us move to the right

Upvote if This Solution helps

Read other posts