[LeetCode] 62. Unique Paths

문제 설명

문제 풀이

• 우선 생각할 점은 결과가 2*10^9이 가능하다는 점에서 완전탐색으로 풀 수 없다는 것이다.
• 특정 규칙을 찾거나 dp를 적용하는 것이 필요한데 아래와 같은 규칙으로 손쉽게 풀 수 있다.

  map[i][j] = map[i-1][j] + map[i][j-1]

소스 코드 (JAVA)

class Solution {
    public int[][] map;

    public int uniquePaths(int m, int n) {
        map = new int[m][];
        for (int i = 0; i < m; i++)
            map[i] = new int[n];

        //계산 시작
        map[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i != 0) map[i][j] += map[i-1][j];
                if (j != 0) map[i][j] += map[i][j-1];
            }
        }

        return map[m-1][n-1];
    }
}