LeetCode＃62. Different paths

subject :

A robot is in a m x n  The top left corner of the grid （ The starting point is marked as “Start” ）.

The robot can only move down or right one step at a time . The robot tries to reach the bottom right corner of the grid （ In the figure below, it is marked as “Finish” ）.

Ask how many different paths there are in total ？

Example 1：

Input ：m = 3, n = 7
Output ：28
Example 2：

 

Input ：m = 3, n = 2
Output ：3
explain ：
From the top left corner , All in all 3 Path to the bottom right .
1. towards the right -> Down -> Down
2. Down -> Down -> towards the right
3. Down -> towards the right -> Down
Example 3：

Input ：m = 7, n = 3
Output ：28
Example 4：

Input ：m = 3, n = 3
Output ：6
 

Tips ：

1 <= m, n <= 100
Question data guarantee that the answer is less than or equal to 2 * 109

source ： Power button （LeetCode）
link ：62. Different paths - Power button （LeetCode） (leetcode-cn.com)

Method 1 （ Permutation and combination ）：

When I first saw this problem, I first thought of it in Mathematics Permutation and combination （ A kind of Combinatorial Mathematics ）_ Baidu Encyclopedia (baidu.com), Many high school students must have done this kind of problem , The method is also relatively simple .

Let's assume that we have to go altogether m+n Step , Then just let one of them m Step right , remainder n Step must be down , The calculation is C(m+n,n)=C(m+n,m).

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        son=min(m-1,n-1);mother=m+n-2
        up=1;down=1
        for i in range(son):
            up*=son-i
        for i in range(son):
            down*=mother-i
        if int(down/up)==0:
            return 1
        else:
            return int(down/up)

Method 2 （ Dynamic programming ）：

Let's suppose we get to the k Step , Then the general method of the previous steps is the first two k-1 Sum of steps （ From the top left to the bottom right can only be the last step, coming from the left or the top , Otherwise it will be meaningless ）, It's just like this in terms of images .

So we need to create a two-dimensional list ：

dp=[]
for i in range(m):
    dp.append([1]*n)  # The default starting values are 1

  After creation , It can be calculated according to this idea , This is similar to Yang Hui's Algorithm LeetCode#118. Yang hui triangle _ As the wind Zhhh The blog of -CSDN Blog

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp=[]
        for i in range(m):
            dp.append([1]*n)
        for i in range(m-1):
            for j in range(n-1):
                dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j]
        return dp[m-1][n-1]