วิธีนำ Backtracking มาใช้ในโจทย์ปีนบันไดใน JavaScript

สมมติว่าเราต้องปีนบันไดที่มี n ขั้น และเราตัดสินใจออกกำลังกายเพิ่มโดยกระโดดขึ้นไป

เราสามารถครอบคลุมได้สูงสุด k ขั้นในการกระโดดครั้งเดียว k จะเป็น 1 หรือ 2 เท่านั้น ไม่ว่าบันไดจะมีกี่ขั้น

เราต้องคืนค่าลำดับการกระโดดที่เป็นไปได้ทั้งหมดที่คุณอาจใช้เพื่อปีนบันได เรียงลำดับแล้ว

เช่น:

for n = 4 and k = 2,

ผลลัพธ์ควรเป็น:

climbingStaircase(n, k) = [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]];

ตัวอย่าง

โค้ดสำหรับนี้จะเป็นดังนี้:

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));

ผลลัพธ์

ผลลัพธ์ในคอนโซลจะเป็นดังนี้:

5