[PS] 99클럽 코테 스터디 40일차 TIL (Unique Paths)

문제

문제 링크

설명

로봇이 격자 왼쪽 상단부터 오른쪽 하단 끝까지 이동하는 경우의 수를 찾는 문제

풀이

1. dp 배열 정의 : (i,j) 영역에 도달하는 경로의 수
   • (i,0) / (0,j) 줄은 경우의 수가 하나뿐이므로 미리 채워 놓는다.
2. 점화식 도출 : 문제에서 로봇은 오른쪽 또는 아래 로 밖에 움직이지 못한다고 했으므로 (i, j) 영역에 도달하는 경우의 수는 왼쪽에서 오는 경우의 수 + 위에서 오는 경우의 수로 나타낼 수 있다.
   • dp[i][j] = dp[i][j - 1] + dp[i - 1][j]

class Solution {
  public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    
    // (i, 0) 채우기
    for (int i = 0; i < m; i++) {
      dp[i][0] = 1;
    }
    // (0, i) 채우기
    for (int i = 0; i < n; i++) {
      dp[0][i] = 1;
    }

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

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