נתאר ביקור בתחנות לאורך מסלול קווי על ידי מערך חד-ממדי stations הכולל מספרים שלמים חיוביים. המספרים מייצגים את תעריפי הביקור בתחנות.
אברהם נמצא בתחנה הראשונה, ומעוניין להגיע לתחנה האחרונה במסלול הזול ביותר האפשרי. כשאברהם נמצא בתחנה i, יש לו שתי אפשרויות: לעבור לתחנה i+1 או לדלג ולעבור ישירות לתחנה i+2.
אם אברהם נמצא בתחנה האחת לפני האחרונה, הוא חייב לעבור לתחנה האחרונה ולא יכול לדלג.
אברהם צריך לשלם תעריפי ביקור בכל תחנה שהוא מבקר בה.
נתון מערך של מספרים שלמים חיוביים stations המייצגים את תעריפי התחנות, יש להחזיר את התשלום הכולל המינימלי שאברהם יכול לשלם כדי להגיע מהתחנה הראשונה אל האחרונה.
לדוגמה, אם המערך stations הוא:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 2 | 8 | 3 | 4 | 7 | 1 | 3 | 2 |
אז יוחזר הערך 12 שהוא הסכום של המספרים 2+3+4+1+2 (המספרים בתחנות שבחרנו מסומנים במערך).
השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.
אין צורך לכתוב מהם תעריפי התחנות שאברהם מבקר בהן, אלא רק את ערכם הכולל.
המערך מלא בנתונים חוקיים.
stations = [2, 8, 3, 4, 7, 1, 3, 2]
12
הסבר: דרך זולה ביותר: 2+3+4+1+2 = 12. כלומר, להתחיל בתחנה 0, לדלג על תחנה 1, לעבור לתחנה 2, ואז תחנה 3, לדלג על תחנה 4, לבקר בתחנה 5, לבקר בתחנה 6, ולסיים בתחנה 7.
stations = [1, 2]
3
הסבר: יש רק שתי תחנות, לכן אברהם חייב לבקר בשתיהן: 1+2 = 3.
stations = [1, 3, 2]
3
הסבר: דרך זולה ביותר: 1+2 = 3. כלומר, להתחיל בתחנה 0, לדלג על תחנה 1, ולסיים בתחנה 2.
stations = [5, 1, 5, 1, 5]
12
הסבר: דרך זולה ביותר: 5+1+1+5 = 12. כלומר, להתחיל בתחנה 0, לבקר בתחנה 1, לדלג על תחנה 2, לבקר בתחנה 3, ולסיים בתחנה 4.
stations = [7, 1, 8, 2, 4]
14
הסבר: דרך זולה ביותר: 7+1+2+4 = 14. כלומר, להתחיל בתחנה 0, לבקר בתחנה 1, לדלג על תחנה 2, ולבקר בתחנות 3 ו-4.
קלט:
stations = [2, 8, 3, 4, 7, 1, 3, 2]
הפלט המבוקש:
12