###### tags: `Leetcode` `medium` `dynamic programming` `python` `Top 100 Liked Questions`

# 62. Unique Paths

## [題目連結:] 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 * 109```.


#### [圖片來源:] https://leetcode.com/problems/unique-paths/

## 解題想法:
兄弟題目:
[63. Unique Paths II](/NLVJwT9dSby6k_l2w-9_Xg)
[64. Minimum Path Sum](/OCDXdY7UT1GY0jZN37TIFA)
* 題目要求從左上走到右下，求走的不同路徑數
* So11_math:
* 總共走了m+n-2步
* 向下走m-1步
* 向右走n-1步
* Sol2_dp:
* dp[i][j]:由(0,0)走到(i,j)的總不同路徑
* 可以簡化，因為每次都繼承上一列的值，所以可以用一維陣列就好
* 二維: dp[i][j]=dp[i-1][j]+dp[i][j-1]
* 一維: dp[i]+=dp[i-1]

DP法: ex m=3 n=7

    1   1   1   1   1   1   1  
    1   2   3   4   5   6   7  
    1   3   6   10  15  21  28  
    該格=左+上

## Python:

import math
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        #法1: 數學 (m+n-2)! / (n-1)! * (m-1)! 
        #return math.factorial(m+n-2)//(math.factorial(m-1)*math.factorial(n-1))
        #法2: DP
        dp=[1]*n
        for _ in range(1,m):
            for i in range(1,n):
                dp[i]+=dp[i-1]
                #dp[i]每次都已經繼承上一列的值了 所以只要再加左邊即可
        return dp[-1]
            

if __name__ == '__main__':
    result = Solution()
    ans = result.uniquePaths(m=3,n=7)
    print(ans)