### 62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Example 1:

Input: m = 3, n = 7Output: 28

Example 2:

Input: m = 3, n = 2Output: 3

Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:

1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Example 3:

Input: m = 7, n = 3Output: 28

Example 4:

Input: m = 3, n = 3Output: 6
• Constraints:
• 1 <= m, n <= 100
• It's guaranteed that the answer will be less than or equal to 2 * 109.

### Analyze

const cache = {}/** * @param {number} m * @param {number} n * @return {number} */var uniquePaths = function (m, n) {  if (m === 1 || n === 1) {    return 1  }
if (cache[${m}~${n}]) {    return cache[${m}~${n}]  } else {    const nums = uniquePaths(m - 1, n) + uniquePaths(m, n - 1)    cache[${m}~${n}] = nums
return nums  }}

/** * @param {number} m * @param {number} n * @return {number} */var uniquePaths = function(m, n) {  const cache = {    [${m - 1}_${n - 1}]: 1  }  for (let x = m - 1; x >= 0; x--) {    for (let y = n - 1; y >= 0; y--) {      if (x === m - 1 && y === n - 1) {        continue      }      if (y + 1 === n) {        cache[${x}_${y}] = cache[${x + 1}_${y}]      } else if (x + 1 === m) {        cache[${x}_${y}] = cache[${x}_${y + 1}]      } else {        cache[${x}_${y}] = cache[${x}_${y + 1}] + cache[${x + 1}_${y}]      }    }  }  return cache['0_0']}

63