טיפוס במדרגות

בכמה דרכים ייחודיות אפשר להגיע לראש גרם מדרגות בן n מדרגות, אם מותר לך לעלות בכל פעם מדרגה אחת או שתיים בלבד?

דוגמה 1:

קלט: n = 2

פלט: 2

הסבר: כדי להגיע לראש גרם מדרגות בן 2 מדרגות, אפשר לעלות מדרגה אחת פעמיים או לעלות 2 מדרגות בבת אחת. לכן יש 2 דרכים שונות להגיע לראש המדרגות.

דוגמה 2:

קלט: n = 3

פלט: 3

הסבר: כדי להגיע לראש גרם מדרגות בן 3 מדרגות, אפשר לעלות מדרגה אחת שלוש פעמים, לעלות מדרגה אחת ואז 2 מדרגות, או לעלות 2 מדרגות ואז מדרגה אחת. לכן יש 3 דרכים שונות להגיע לראש המדרגות.

דוגמה 3:

קלט: n = 4

פלט: 5

הסבר: כדי להגיע לראש גרם מדרגות בן 4 מדרגות, הנה 5 האפשרויות: 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 2. כל מספר מייצג עלייה של מדרגה אחת או שתיים בכל פעם, ולסדר יש חשיבות.