[리트코드] 62. Unique Paths

문제

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

Unique Paths - LeetCode

---

해결 방안

동적 프로그래밍 문제이며 공식과 같은 문제라고 생각합니다.

 

 

우선 만약 아래와 같은 상황이 있다고 생각합시다.

이 이미지와 같이

grid[1][100]이라도 finish에 도착할 수 있는 경우의 수는 1번이고

grid[100][1]이라도 finish에 도착할 수 있는 경우의 수는 1번입니다.

 

이 정보를 토대로 Example 1풀이에 대해 설명해보겠습니다.

Example 1:

Input: m = 3, n = 7
Output: 28

 

이와 같은 경우면 위에 설명했던 내용을 적용해보면

• grid[0][0] ~ grid[0][7] = 1
• grid[0][0] ~ grid[2][0] = 1

1이 됩니다.

이렇게요.

이제 나머지 빈칸일 경우 경의 위치에 있을 때 finish에 도착할 수 있는 경우의 수를 구해야 되는데요.

구하는 방법은 간단합니다.

 

구해야 되는 위치가 grid[i][j]이면 g[i-1][j] + g[i][j-1]을 해주면 됩니다.

•  grid[i][j] = g[i-1][j] + g[i][j-1]

 grid[i][j] = g[i-1][j] + g[i][j-1]이방식을 for문으로 돌리면 아래와 같은 이미지대로 됩니다.

---

소스코드

var uniquePaths = function(m, n) {
    const grid = new Array(m);
    for(let i=0; i<m; i++) grid[i] = new Array(n).fill(1);
    
    for(let i=1; i<m; i++){
        for(let j=1; j<n; j++) grid[i][j] = grid[i-1][j] + grid[i][j-1];
    }
    
    return grid[m-1][n-1]
};

---

알고리즘 순서도