:orphan:

Unique Paths
============

.. highlight:: none

Problem
-------
https://leetcode.com/problems/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``\ :sup:```9```.

 

**Example 1:**

|image1|

::


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

**Example 2:**

::


   Input: m = 3, n = 2
   Output: 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

 

**Constraints:**

- ``1 <= m, n <= 100``

.. |image1| image:: https://assets.leetcode.com/uploads/2018/10/22/robot_maze.png

.. highlight:: python

Pattern
-------
Math, Dynamic Programming, Combinatorics

Approaches
----------

.. tab-set::

    .. tab-item:: Dynamic Programming

        **Code**

        .. literalinclude:: ../problems/medium/unique-paths/unique_paths__dynamic_programming.py
            :language: python
            :lines: 10-

        **Test**

        >>> from unique_paths__dynamic_programming import uniquePaths
        >>> uniquePaths(3, 7)
        28
        >>> uniquePaths(3, 2)
        3

        .. autofunction:: unique_paths__dynamic_programming.uniquePaths