คำอธิบายปัญหา
มีบันได n ขั้น คนหนึ่งจะเดินจากขั้นที่ 1 ถึงขั้นที่ n จำนวนขั้นสูงสุดที่เขา/เธอสามารถข้ามได้ในหนึ่งก้าว ก็ได้รับการกำหนด ด้วยข้อมูลนี้ เราต้องหาวิธีที่เป็นไปได้ในการไปถึงขั้นที่ n สมมติว่าข้ามได้สูงสุด 2 ขั้นต่อก้าว เราสามารถหาความสัมพันธ์เวียนได้ วิธีไปถึงขั้น n คือมาจากขั้น (n-1) หรือขั้น (n-2) ดังนั้น ways(n) = ways(n-1) + ways(n-2)
สมมติจำนวนขั้นคือ 10 จำนวนขั้นสูงสุดที่กระโดดได้ในหนึ่งก้าวคือ 2 ผลลัพธ์จะเป็น 89 วิธี
เพื่อแก้ปัญหานี้ ทำตามขั้นตอนเหล่านี้:
- กำหนดอาร์เรย์ count ขนาดเท่าจำนวนขั้น
- count[0] := 1
- for i := 2 to stair -1, do
- count[i] := 0
- for j = 1 to i and j <= max; do
- count[i] := count[i] + count[i - j]
- คืนค่า count[stair - 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
