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.
classSolution { fununiquePaths(m: Int, n: Int): Int { var grid = Array(m) { IntArray(n) { 0 } }
for (i in0 until m) { grid[i][0] = 1 } for (i in0 until n) { grid[0][i] = 1 } for (i in1 until m) { for (j in1 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
classSolution { fununiquePaths(m: Int, n: Int): Int { var N = n + m - 2 var R = m - 1 var result = 1L
for (i in1 .. R) { result = result * (N - R + i) / i } return result.toInt() } }
Point of Thinking
가장 위의 행과 왼쪽의 열을 1로 초기화한 후 배열을 순회하면서 위와 왼쪽의 합으로 초기화하면 되는 문제
기본적으로 경로를 탐색할때 모든 경우의 수를 계산하는 기초적인 방법이다.
보다 조금 수학적으로 푼다면 순열조합 공식을 쓸 수 있다.
한 개의 행 또는 열의 길이를 n개라고 할때 r개의 시작 경로를 고르는 순열 공식은 아래와 같이 유도할 수 있다.
nPr=n(n−1)(n−2)⋅⋅⋅(n−(r−1))=(n−r)!n!
이를 기반으로 조합 공식을 떠올려보면 한 개의 행 또는 열의 길이를 n개라고 할때 r개의 시작 경로를 고르는 순열 공식 을 r개의 시작 경로를 고르는 경우의 수 로 나누는 것을 기억하자.