มีบันได n ขั้น คนหนึ่งจะขึ้นบันไดที่ 1 ถึง n กำหนดจำนวนบันไดสูงสุดที่เขา/เธอสามารถข้ามได้ในขั้นตอนเดียว จากข้อมูลนี้ เราต้องหาวิธีที่เป็นไปได้ในการขึ้นบันไดที่ n ให้เราพิจารณาว่าแต่ละขั้นสามารถข้ามบันไดได้สูงสุดสองขั้น ดังนั้นเราจึงสามารถหาความสัมพันธ์แบบเรียกซ้ำเพื่อแก้ปัญหานี้ได้ หนึ่งสามารถย้ายไปที่บันไดที่ n ไม่ว่าจะจากบันไดที่ (n-1) หรือจากบันไดที่ (n-2) ดังนั้น วิธี(n) =วิธี(n-1) + วิธี(n-2)
สมมุติว่าจำนวนขั้นบันไดคือ 10 จำนวนขั้นบันไดสูงสุดที่สามารถกระโดดได้ในขั้นตอนเดียว พูดเป็น 2 แล้วเอาท์พุตจะเป็น 89 วิธี
ในการแก้ปัญหานี้ ให้ทำตามขั้นตอนเหล่านี้ -
- กำหนดจำนวนอาร์เรย์ที่มีขนาดเท่ากับหมายเลขขั้นบันได
- นับ[0] :=1
- สำหรับ i :=2 ขึ้นบันได -1 ทำ
- นับ[i] :=0
- สำหรับ j =1 ถึง i และ j <=สูงสุด; ทำ
- นับ[i] :=นับ[i] + นับ[i - j]
- นับคืน[บันได - 1]
มาดูการใช้งานกันให้เกิดความเข้าใจกันมากขึ้น
ตัวอย่าง (C++)
#include<iostream>
using namespace std;
int stairClimbWays(int stair, int max){
int count[stair]; //fill the result stair using bottom up manner
count[0] = 1; //when there are 0 or 1 stair, 1 way to climb
count[1] = 1;
for (int i=2; i<stair; i++){ //for stair 2 to higher
count[i] = 0;
for(int j=1; j<=max && j<=i; j++)
count[i] += count[i-j];
}
return count[stair-1];
}
int countWays(int stair, int max){ //person can climb 1,2,...max stairs at a time
return stairClimbWays(stair+1, max);
}
int main (){
int stair, max;
cout << "Enter number of stairs: "; cin >> stair;
cout << "Enter max stair a person can climb: "; cin >> max;
cout << "Number of ways to reach: " << countWays(stair, max);
} อินพุต
Stairs = 10 Max stairs a person can climb: 2
ผลลัพธ์
Enter number of stairs: 10 Enter max stair a person can climb: 2 Number of ways to reach: 89
