(Leet Code JS)Unique Paths

https://leetcode.com/problems/unique-paths/

Unique Paths - LeetCode

 

DP 알고리즘.

m x n 크기의 배열을 선언하고 0으로 초기화한다.

[0, 0] 좌표에서 [m - 1, n - 1] 좌표까지 갈 수 있는 방법을 모두 구하는데,

[0, 0]은 1로 시작하고 이중 for문으로 DP를 적용한다.

 

로봇은 오른쪽 또는 아래로 가기 때문에 순회를 하면서 점화식을 적용한 값을 배열에 저장하면 된다.

점화식은

DP[i][j] = DP[i - 1][j] + DP[i][j - 1]이 된다.

예외 처리가 필요한 부분이 있다.

 

0행은 위에서 오는 경로가 없기 때문에 DP[i][j] += DP[i][j - 1] 로 진행한다.

또한, i !== 0 && j === 0 인 경우, 왼쪽에서 오는 경로가 없기 때문에 DP[i][j] += DP[i - 1][j]로 적용한다.

 

그 외 나머지는 일반 점화식을 적용해 값을 구할 수 있다.

const uniquePaths = (m, n) => {
    const dp = Array.from({length: m}, () => Array(n).fill(0));
    
    dp[0][0] = 1;
    
    for(let i = 0; i < m; i++){
        for(let j = 0; j < n; j++){
            if(i === 0){
                if(j === 0){
                    continue;
                } else {
                    dp[i][j] += dp[i][j - 1];
                }
            } else{
                if(j === 0){
                    dp[i][j] += dp[i - 1][j];
                } else{
                    dp[i][j] += (dp[i - 1][j] + dp[i][j - 1]);
                }
            }
        }
    }
    
    return dp[m - 1][n - 1];
};