Giả sử chúng ta cần leo lên một cầu thang có n bậc và chúng ta quyết định tập thêm một chút bằng cách nhảy lên các bậc.
Chúng ta có thể thực hiện nhiều nhất k bước trong một bước nhảy. k sẽ là 1 hoặc 2 bất kể số bậc trong cầu thang.
Chúng tôi được yêu cầu trả lại tất cả các chuỗi nhảy có thể có mà bạn có thể thực hiện để leo lên cầu thang, đã được sắp xếp.
Ví dụ -
for n = 4 and k = 2,
đầu ra phải là -
climbingStaircase(n, k) = [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]];
Ví dụ
Mã cho điều này sẽ là -
const n = 4;
const climbStairs = (n) => {
if (n == 0) return 0;
let memory = new Map();
let recur = (left) => {
if (memory.has(left)) return memory.get(left);
if (left <= 0) return 0;
if (left == 1) return 1;
if (left == 2) return 2;
memory.set(left, recur(left − 2) + recur(left − 1));
return memory.get(left);
};
return recur(n);
};
console.log(climbStairs(n)); Đầu ra
Và đầu ra trong bảng điều khiển sẽ là -
5