(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

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

Example 3

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

Example 4

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

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

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개의 시작 경로를 고르는 순열 공식은 아래와 같이 유도할 수 있다.

$_n P _r = n(n - 1)(n-2) \cdot\cdot\cdot (n - (r - 1)) = \cfrac{n!}{(n-r)!}$

• 이를 기반으로 조합 공식을 떠올려보면 한 개의 행 또는 열의 길이를 n개라고 할때 r개의 시작 경로를 고르는 순열 공식 을 r개의 시작 경로를 고르는 경우의 수 로 나누는 것을 기억하자.

$_n C _r = \cfrac{_n P _r}{r!} = \cfrac{\cfrac{n!}{(n-r)!}}{r!} = \cfrac{n!}{r!(n-r)!}$

• 이 공식을 이번 문제에 적용하면 아래와 같이 유도할 수 있다.

$_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!}$

• 이를 코드로 변환하면 아래와 같다.

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
}