[leetcode]62. Unique Paths

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?

Above is a 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

 

Example 1:

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 -> Right -> Down   2. Right -> Down -> Right    3. Down -> Right -> Right

 

Example 2:

Input: m = 7, n = 3

Output: 28

 

Solution 1 :

중학교때 배운 최단거리 경우의수 구하는방식

class Solution(object):
    def uniquePaths(self, m, n):
        paths = [[0]*m for _ in range(n)]
        paths[0][0] = 1
        for i in range(n):
            for j in range(m):
                if i==0 and j ==0 :
                    continue
                paths[i][j] += paths[i-1][j] if i>0 else 0
                paths[i][j] += paths[i][j-1] if j>0 else 0
        
        return paths[i][j]

Solution 2:

순열을 이용한 방법

같은 것 p개 q개 r개 있는 n개의 것을 순서를 생각하며 나열하는 경우의 수는 

n! /(p! * q! * n!)

class Solution(object):
    def uniquePaths(self, m, n):
        return self.factorial(m+n-2) / (self.factorial(m-1) * self.factorial(n-1))
    
    def factorial(self, n):
        num = 1
        while n >= 1:
            num = num * n
            n = n - 1
        return num