설명:

This problem was asked by Amazon.
N개의 계단이 존재하며 한 번에 1개 또는 2개의 계단을 오를 수 있습니다. N이 주어지면 계단을 오를 수 있는 고유한 방법의 수를 반환하는 함수를 작성하세요. 단계의 순서가 중요합니다.

예시:

예를 들어, N가 4인 경우 5 고유한 방법이 있습니다.

1, 1, 1, 1

2, 1, 1

1, 2, 1

1, 1, 2

2, 2

피보나치:

N = [0, 1, 2, 3, 4, 5, 6]Output Ways = [1, 1, 2, 3, 5, 8, 13]출력의 피보나치.

추가의:

한 번에 1~2계단을 오르는 대신 양의 정수 집합 X에서 임의의 숫자를 오를 수 있다면 어떨까요? 예를 들어 X = [1, 3, 5] 이면 한 번에 1 , 3 또는 5 단계를 오를 수 있습니다.

JS 솔루션:

O(n * m)

n --> 계단 계단 ( N )

m --> 유효한 계단 오르기( X.length )

let staircase = (n, X) => {

    // Steps climb up
    let setX = new Set(X)

    // Positions arrays step staircase
    // Included  0  
    let cache = Array(n + 1).fill(0);

    // The position 0 is always 1 way.
    cache[0] = 1;


    for (let i = 0; i <= n; ++i) {

        let temp = 0;

        // Valid Steps add
        for (let x of X) {
            if (i - x > 0) {
                temp += cache[i - x]
            }
        }

        //Update cache.
        cache[i] += temp;
        // position numbers 
        // is included (1) or not (0)
        cache[i] += setX.has(i) ? 1 : 0;
    }

    // The last position in cache have the
    // # of ways.
    return cache.pop();
}

간단한 테스트:

// Case 1
let X = [1, 2 ];
let n = 4;

console.log(staircase(n, X))

// Case 2 
let X = [1, 3, 5];
let n = 4;

console.log(staircase(n, X))

당신은 확인할 수 있습니다
code 의해