Description

62. Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 10^9.

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

Constraints:

• 1 <= m, n <= 100

---

62. 유니크 패스

m x n 격자에 로봇이 있습니다. 로봇은 처음에 왼쪽 상단 모서리(즉, grid[0][0])에 위치합니다. 로봇은 오른쪽 하단 모서리(즉, grid[m - 1][n - 1])로 이동하려고 합니다. 로봇은 어느 시점에서나 아래쪽이나 오른쪽으로만 이동할 수 있습니다.

두 정수 m과 n이 주어졌을 때, 로봇이 오른쪽 하단 모서리에 도달할 수 있는 가능한 고유 경로의 수를 반환합니다.

테스트 케이스는 답이 2 * 10^9 이하가 되도록 생성됩니다.

예제 1:

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

예제 2:

입력: m = 3, n = 2
출력: 3
설명: 왼쪽 상단 모서리에서 시작하여, 오른쪽 하단 모서리에 도달하는 총 3가지 방법이 있습니다:
1. 오른쪽 -> 아래 -> 아래
2. 아래 -> 아래 -> 오른쪽
3. 아래 -> 오른쪽 -> 아래

제약 조건:

• 1 <= m, n <= 100

Solution

class Solution {
    private static final int INITIAL_PATH_COUNT = 1;
    private static final int NOT_CALCULATED = 0;

    public int uniquePaths(int m, int n) {
        int[][] pathCount = new int[m][n];
        pathCount[m - 1][n - 1] = INITIAL_PATH_COUNT;

        return calculatePaths(pathCount, m, n, 0, 0);
    }

    private int calculatePaths(int[][] pathCount, int m, int n, int row, int col) {
        // 이미 계산된 경로의 수가 있다면 반환
        if (pathCount[row][col] != NOT_CALCULATED) {
            return pathCount[row][col];
        }

        // 마지막 행이 아니라면, 아래쪽 경로 탐색
        if (row < m - 1) {
            pathCount[row][col] += calculatePaths(pathCount, m, n, row + 1, col);
        }

        // 마지막 열이 아니라면, 오른쪽 경로 탐색
        if (col < n - 1) {
            pathCount[row][col] += calculatePaths(pathCount, m, n, row, col + 1);
        }

        return pathCount[row][col];
    }
}