โปรแกรมตรวจสอบจำนวนวิธีที่เราสามารถย้าย k ครั้งและกลับสู่ที่แรกใน python

สมมติว่าเราอยู่ที่ตำแหน่ง 0 ของรายการความยาว n และในแต่ละขั้นตอน เราสามารถย้ายไปทางขวาที่หนึ่งหรือซ้ายหนึ่งที่ (ไม่เกินขอบเขต) หรืออยู่ที่ตำแหน่งเดิม ตอนนี้ถ้าเราสามารถเดินได้ k ก้าว เราต้องค้นหาว่าเราจะเดินได้กี่ก้าวและย้อนกลับไปที่ดัชนี 0 หากคำตอบคือมาก ให้คืนค่า mod 10^9 + 7

ดังนั้น หากอินพุตเป็น n =7 k =4 เอาต์พุตจะเป็น 9 ตามการกระทำ -

• [ขวา ขวา ซ้าย ซ้าย],
• [ขวา ซ้าย ขวา ซ้าย]
• [อยู่ อยู่ อยู่ อยู่]
• [ขวา ซ้าย อยู่ อยู่]
• [อยู่ อยู่ ขวา ซ้าย]
• [ขวา อยู่ อยู่ ซ้าย]
• [ขวา อยู่ ซ้าย อยู่]
• [อยู่ ขวา ซ้าย อยู่]
• [อยู่ ขวา อยู่ ซ้าย]

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

• ม :=10^9 + 7
• N :=ความยาว
• กำหนดฟังก์ชัน dp() นี่จะใช้เวลาฉันกระโดด
• ถ้ากระโดดเหมือนกับ 0 แล้ว
  • คืนค่า (จริงเมื่อฉันเหมือนกับ 0 มิฉะนั้นเป็นเท็จ)
• นับ :=dp(i, กระโดด - 1)
• ถ้า i>=0 แล้ว
  • นับ :=นับ + dp(i + 1 กระโดด - 1)
• ถ้าฉัน <=N - 1 แล้ว
  • นับ :=นับ + dp(i - 1 กระโดด - 1)
• จำนวนคืนสินค้า
• จากวิธีหลัก ให้ทำดังนี้:
• คืนค่า dp(0, n) mod m

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

ตัวอย่าง

class Solution:
   def solve(self, length, n):
      MOD = 10 ** 9 + 7
      N = length

      def dp(i, jumps):
         if jumps == 0:
            return +(i == 0)

         count = dp(i, jumps - 1)
         if i >= 0:
            count += dp(i + 1, jumps - 1)
         if i <= N - 1:
            count += dp(i - 1, jumps - 1)
         return count
      return dp(0, n) % MOD    
ob = Solution()
n = 7
k = 4
print(ob.solve(n, k))

อินพุต

7, 4

ผลลัพธ์

9