(LeetCode) 62. Unique Paths

62. Unique Paths

  • Explore : Interview > Top Interveiw Questions > Medium Collection
  • 분류 : Dynamic Programming
  • 난이도 : Medium

Problem

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

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

Example 2

1
2
3
4
5
6
7
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

Example 3

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

Example 4

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

Constraints

  • 1 <= m, n <= 100
  • It’s guaranteed that the answer will be less than or equal to 2 * 10^9.

Solution (Memoization)

Exapnder
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
fun uniquePaths(m: Int, n: Int): Int {
var grid = Array(m) {
IntArray(n) { 0 }
}

for (i in 0 until m) {
grid[i][0] = 1
}
for (i in 0 until n) {
grid[0][i] = 1
}
for (i in 1 until m) {
for (j in 1 until n) {
grid[i][j] = grid[i - 1][j] + grid[i][j - 1]
}
}
return grid[m - 1][n - 1]
}
}

Solution (Mathematics)

Exapnder
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
fun uniquePaths(m: Int, n: Int): Int {
var N = n + m - 2
var R = m - 1
var result = 1L

for (i in 1 .. R) {
result = result * (N - R + i) / i
}
return result.toInt()
}
}

Point of Thinking

  • 가장 위의 행과 왼쪽의 열을 1로 초기화한 후 배열을 순회하면서 위와 왼쪽의 합으로 초기화하면 되는 문제
  • 기본적으로 경로를 탐색할때 모든 경우의 수를 계산하는 기초적인 방법이다.
  • 보다 조금 수학적으로 푼다면 순열조합 공식을 쓸 수 있다.
  • 한 개의 행 또는 열의 길이를 n개라고 할때 r개의 시작 경로를 고르는 순열 공식은 아래와 같이 유도할 수 있다.
nPr=n(n1)(n2)(n(r1))=n!(nr)!_n P _r = n(n - 1)(n-2) \cdot\cdot\cdot (n - (r - 1)) = \cfrac{n!}{(n-r)!}
  • 이를 기반으로 조합 공식을 떠올려보면 한 개의 행 또는 열의 길이를 n개라고 할때 r개의 시작 경로를 고르는 순열 공식r개의 시작 경로를 고르는 경우의 수 로 나누는 것을 기억하자.
nCr=nPrr!=n!(nr)!r!=n!r!(nr)!_n C _r = \cfrac{_n P _r}{r!} = \cfrac{\cfrac{n!}{(n-r)!}}{r!} = \cfrac{n!}{r!(n-r)!}
  • 이 공식을 이번 문제에 적용하면 아래와 같이 유도할 수 있다.
nCr=nPrr!=n(n1)(n2)(n(r1))r!=n(n1)(n2)(nr+1)r!=(nr+1)(nr+2)(n1)nr!_n C _r \\ = \cfrac{_n P _r}{r!} = \cfrac{n(n - 1)(n-2) \cdot\cdot\cdot (n - (r - 1))}{r!} \\ = \cfrac{n(n - 1)(n-2) \cdot\cdot\cdot (n - r + 1)}{r!} \\ = \cfrac{(n - r + 1)(n - r + 2) \cdot\cdot\cdot (n - 1)n}{r!}
  • 이를 코드로 변환하면 아래와 같다.
1
2
3
4
5
6
7
8
var N = n + m - 2 // 모든 경우의 수 n
var R = m - 1 // 선택할 경우의 수 r

var result = 1
for (i in 1 .. R) { // Factorial
result = result * (N - R + i) / i
}