[다시풀기/릿코드/javascript] 62. Unique Paths

<나의 풀이>

1. 계산을 쉽게하기 위해 작은것을 m으로 둔다.

2. m===1일경우 방법은 1개이다.

3. m===2일 경우 방법은 n개이다.(한번만 밑으로 내려갈 수 있는데 이걸 n개중에 고를 수 있다.)

4. m===3일 경우 방법은 1부터 n까지 모든 수의 합이다. 

5. m>3일 경우 m===3이 될때까지 m-1을 해가며 재귀로 더해주면 된다.

var uniquePaths = function(m, n) {
    if(m>n){
        let temp = m;
        m = n;
        n = temp;
    }
    if(m===1) return 1;
    if(m===2) return n;
    if(m===3) {
        let sum = 0;
        for(let i=1;i<=n;i++){
            sum+=i
        }
        return sum;
    }
    //n을 다 더하되.... m===3이 될때까지 n을 빼야함.
    let sum = 0;
    for(let i=1;i<=n;i++){
        sum+=uniquePaths(m-1,i)
    }
    return sum
};

 다만 이 방법은 속도가 아주아주 느리다!!

이 규칙을 알아내라 애썼는데 ㅎㅎ 더욱 간단한 풀이법이 있었다.

 

var uniquePaths = function(m, n) {
    let map = new Array(m).fill([]).map(()=>new Array(n).fill(1))
    for(let y=1;y<m;y++){
        for(let x=1;x<n;x++){
            map[y][x] = map[y-1][x]+map[y][x-1]
        }
    }
    return map[m-1][n-1]
};

훨씬 간단한 dp를 이용한 풀이법!

map[y][x] = map[y-1][x]+map[y][x-1]임을 이용하였다!!