LeetCode : 62. Unique Paths

문제

$m\times n$ 모양의 격자판 위에 로봇이 있다. 로봇은 시작점인 왼쪽 위 모서리에서부터 도착점인 오른쪽 아래 모서리로 가려고 하는데, 한 번에 아래로 한 칸 혹은 오른쪽으로 한 칸만 움직일 수 있다.
$m, n$이 주어지면 도착점에 갈 수 있는 방법의 총 가짓수를 구하여라.

제약 조건

• 1 $\le m, n \le$ 100
• $m, n$은 출력이 $2\times10^9$를 넘지 않도록 주어진다

예시

입력 : m=3, n=7
출력 : 28

풀이

LeetCode 70. Climbing Stairs과 같은 문제다.

• 주어진 $m, n$에 대하여 도착할 수 있는 가짓수를 $f(m, n)$라고 정의
• 오른쪽으로 한 칸 움직이는 경우와 아래로 한 칸 움직이는 경우 두 가지로 분해할 수 있다

$f(m, n) = f(m-1, n) + f(m, n-1)$

1. 기저 사례 처리

if (m <= 1 || n <= 1) {
    return 1;
}

2. 재귀 함수 구현

class Solution {
public:
    int uniquePaths(int m, int n) {
        if (m <= 1 || n <= 1) {
            return 1;
        }

        return uniquePaths(m-1, n) + uniquePaths(m, n-1);
    }
};

3. Memoization 적용

class Solution {
public:
    int cache[101][101] = {0, };
    int uniquePaths(int m, int n) {
        if (m <= 1 || n <= 1) {
            return 1;
        }

        int& ret = cache[m][n];
        if(ret != 0) return ret;
        else{
            ret = uniquePaths(m-1, n) + uniquePaths(m, n-1);
            return ret;
        }
    }
};