Leetcode - 62. Unique Paths

문제

mxn 크기의 맵이 주어질때 좌상단에서 우하단으로 갈수있는 모든 경우의 수를 구하기.

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

https://leetcode.com/problems/unique-paths/

해결 brute force

우선 각각의 위치는 왼쪽칸 + 윗칸 값이 될것이다. 그리고 가장 코너칸의 값은 갈수있는방법이 1가지이기때문에 1이다. 그렇게 점화식을 세우면 다음과 같다.
f(m,n) = f(m-1, n) + f(m, n-1)
결과는 시간초과

/* brute force */

int uniquePaths(int m, int n){
    /* base case */
    if (m == 1 || n == 1) return 1;
    /* recursive */
    return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
}

해결 DP top-down

visited[][] 배열에 계산된 값을 저장하는 memoization 으로 속도 개선.

/* DP top-down */
int visited[101][101];
int uniquePaths(int m, int n){
    /* base case */
    if (visited[m][n])
        return visited[m][n];
    if (m == 1 || n == 1) return 1;
    /* recursive */
    visited[m][n] = uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    return visited[m][n];
}

해결 DP bottom-up

동일문제를 recursive가 아닌 for loop로 해결. 시간복잡도는 동일

/* DP bottom-up */
int uniquePaths(int m, int n){
    int ret[101][101] = {0};
    
    for (int i = 1; i <= m; i++)
        ret[i][1] = 1;
    for (int j = 1; j <= n; j++)
        ret[1][j] = 1;
    for (int i = 2; i <= m; i++) {
        for (int j = 2; j <= n; j++) {
            ret[i][j] = ret[i - 1][j] + ret[i][j - 1];
        }
    }
    return ret[m][n];
}