[LeetCode] 62. Unique Paths

이동에 필요한 경우의 수를 계산하기 위해 첫 번째 열과 행을 1로 초기화하고, 초기화 된 셀을 기준으로 위, 왼쪽 방향의 경우의 수를 합산해 현재 셀의 경우의 수를 계산할 수 있음

최종적으로 우측 하단의 셀 값을 통해 가능한 경우의 수를 알 수 있다.

😎풀이

function uniquePaths(m: number, n: number): number {
    // 2D 배열 초기화
    const dp = Array.from({ length: m }, () => Array(n).fill(0))
    
    // 첫 번째 행과 열을 1로 초기화
    for (let i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (let j = 0; j < n; j++) {
        dp[0][j] = 1;
    }
    
    // 나머지 셀 채우기
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    
    // 오른쪽 하단 셀의 값 반환
    return dp[m-1][n-1];
}