62. Unique Paths

우선 m이 row를 뜻하므로 1줄이라면 별까지 가는 경우의 수는 1개일 수밖에 없다.

1줄이 아니라면 옛날에 그 미로찾기같은거 할 때 경우의 수 구하는 방법에서 여기까지 오는데 가능한 경우의 수를 써놓고 한칸전진하면 이전 경우의 수들 더해서 작성하는 그 방식으로 문제를 풀었다.

const uniquePaths = function(m, n) {
    if (m == 1) return 1;

    const arr = Array.from ({length: m}, () => Array.from ({length: n} , () => 0)) 

    for (let i = 0 ; i < n ; i++) {
        arr[0][i] = 1
    }

    for (let i = 0 ; i < m ; i++) {
        arr[i][0] = 1
    }


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

결국 dp 문제

const uniquePaths = function(m, n) {
    let dp = new Array(m).fill(0).map(() => new Array(n));

    for(let row = m - 1; row >= 0; row--) {
        for(let col = n - 1; col >= 0; col--) {
            if(row === (m - 1) || col === (n - 1)) dp[row][col] = 1;
            else dp[row][col] = dp[row + 1][col] + dp[row][col + 1];
        }
    }
    return dp[0][0];
};