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

### 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[int]int{})
}
func pathFinder(m int, n int, dp map[int]int) int {
var pos = 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