Today I Learned

오늘도 java 코테 공부!

Unique Paths

Leetcode 62 https://leetcode.com/problems/unique-paths/description/

문제

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.

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

풀이 과정

• 왼쪽 위 모서리에서 오른쪽 아래 모서리로 이동하는 방법의 수를 계산하는 문제로 DP를 이용해 풀었다.

1. 격자 크기가 1x1인 경우 1을 반환하게 한다.

2. 각 셀에 도달할 수 있는 고유한 경로 수를 저장하기 위해 2차원배열을 선언한다.

3. 가장자리 셀들은 오른쪽이나 아래쪽으로만 이동할 수 있으므로 경우의 수가 1이다.

4. 내부의 셀들은 2중 for문으로 고유한 경로의 수를 계산한다. 왼쪽셀과 위쪽 셀에서 오는 경로 수를 합산한다.

5. 목표 지점까지 도달하는 고유한 경로의 수를 반환하면 완료!

Java 코드

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

    int[][] dp = new int[m][n];

    for (int i = 0; i < m; i++) {
      dp[i][0] = 1;
    }
    for (int j = 0; j < n; j++) {
      dp[0][j] = 1;
    }

    for (int i = 1; i < m; i++) {
      for (int j = 1; j < n; j++) {
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      }
    }
    
    return dp[m - 1][n - 1];
  }