โปรแกรมหาจำนวนวิธีที่เราสามารถขึ้นบันไดได้ (ขั้นบันไดสูงสุดไม่เกิน k ครั้ง) ใน Python

สมมุติว่าเรามีบันไดที่มี n ขั้น และเราก็มี k อีกตัวด้วย ตอนแรกเราอยู่ที่บันได 0 และเราสามารถปีนขึ้นไปทีละ 1, 2 หรือ 3 ขั้นได้ แต่เราสามารถขึ้นบันไดได้เพียง 3 ขั้นเท่านั้น ไม่เกิน k ครั้ง ตอนนี้เราต้องหาหลายวิธีที่จะขึ้นบันไดได้

ดังนั้นหากอินพุตเป็น n =5, k =2 เอาต์พุตจะเป็น 13 เนื่องจากเราสามารถขึ้นบันไดได้หลายวิธี -

• [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]
• [1, 1, 3]
• [1, 3, 1]
• [3, 1, 1]
• [2, 3]
• [3, 2]

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

• ถ้า n เหมือนกับ 0 แล้ว
  • คืน 1
• ถ้า n เหมือนกับ 1 แล้ว
  • คืน 1
• k:=ขั้นต่ำของ k, n
• บันทึก:=เมทริกซ์ขนาด (n+1) x (k+1)
• สำหรับ r ในช่วง 0 ถึง k ทำ
  • บันทึก[r, 0]:=1 บันทึก[r, 1]:=1 บันทึก[r, 2]:=2
• สำหรับฉันในช่วง 3 ถึง n ทำ
  • บันทึก[0, i]:=บันทึก[0, i-1] + บันทึก[0, i-2]
• สำหรับ j ในช่วง 1 ถึง k ทำ
  • สำหรับฉันในช่วง 3 ถึง n ทำ
    • จำนวน :=ผลหารของ i/3
    • ถ้านับ <=j แล้ว
      • บันทึก[j, i]:=บันทึก[j, i-1] + บันทึก[j, i-2] + บันทึก[j, i-3]
    • มิฉะนั้น
      • บันทึก[j, i]:=บันทึก[j, i-1] + บันทึก[j, i-2] + บันทึก[j-1, i-3]
• return memo[k, n]

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

ตัวอย่าง

class Solution:
   def solve(self, n, k):
      if n==0:
         return 1
      if n==1:
         return 1
         k= min(k,n)
         memo=[[0]*(n+1) for _ in range(k+1)]
         for r in range(k+1):
            memo[r][0]=1
            memo[r][1]=1
            memo[r][2]=2
            for i in range(3,n+1):
               memo[0][i]=memo[0][i-1]+memo[0][i-2]
               for j in range(1,k+1):
                  for i in range(3,n+1):
                     count = i//3
                     if count<=j:
                        memo[j][i]=memo[j][i-1]+memo[j][i-2]+memo[j][i-3]
                     else:
                        memo[j][i]=memo[j][i-1]+memo[j][i-2]+memo[j-1][i-3]
         return memo[k][n]
ob = Solution()
print(ob.solve(n = 5, k = 2))

อินพุต

5, 2

ผลลัพธ์

13