โปรแกรมหาทางขึ้นบันไดใน Python

สมมติว่าเรามีบันไดที่มี n ขั้น และเราสามารถปีนขึ้นไปทีละ 1 หรือ 2 ขั้นก็ได้ เราต้องกำหนดฟังก์ชันที่คืนค่าจำนวนวิธีที่ไม่ซ้ำกันในการขึ้นบันได

ลำดับของขั้นตอนไม่ควรเปลี่ยนแปลง ดังนั้นแต่ละลำดับของขั้นตอนที่ต่างกันจึงนับเป็นวิธีหนึ่ง หากคำตอบมีขนาดใหญ่มาก ให้แก้ไขผลลัพธ์ด้วย 10^9 + 7

ดังนั้นหากอินพุตเป็น n =5 เอาต์พุตจะเป็น 8 เนื่องจากมี 8 วิธีที่ไม่ซ้ำกัน -

• 1, 1, 1, 1, 1
• 2, 1, 1, 1
• 1, 2, 1, 1
• 1, 1, 2, 1
• 1, 1, 1, 2
• 1, 2, 2
• 2, 1, 2
• 2, 2, 1

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• dp:=อาร์เรย์ขนาด n+1 และเติม 0
• dp[1]:=1
• สำหรับ i ในช่วง 2 ถึง n+1 ให้ทำ
  • dp[i]:=dp[i-1]+dp[i-2]
• คืนค่าองค์ประกอบสุดท้ายของ dp mod m

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

m =(10**9)+7
class Solution:
   def solve(self, n):
      dp=[0 for _ in range(n+2)]
      dp[1]=1
      for i in range(2,n+2):
         dp[i]=dp[i-1]+dp[i-2]
      return dp[-1] % m
ob = Solution()
print(ob.solve(5))

อินพุต

5

ผลลัพธ์

8