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

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

เช่น n = 7, k = 4 ผลลัพธ์ 9 วิธี เช่น [Right, Right, Left, Left], [Stay, Stay, Stay, Stay] เป็นต้น

ขั้นตอนการแก้ปัญหา

• MOD := 10^9 + 7
• N := length
• กำหนดฟังก์ชัน dp(i, jumps):
  • ถ้า jumps == 0 คืนค่า 1 ถ้า i==0 มิฉะนั้น 0
  • count := dp(i, jumps-1) (อยู่ที่เดิม)
  • ถ้า i > 0 เพิ่ม dp(i-1, jumps-1) (เดินซ้าย)
  • ถ้า i < N-1 เพิ่ม dp(i+1, jumps-1) (เดินขวา)
  • คืนค่า count
• จากเมธอดหลัก คืนค่า dp(0, n) % MOD

ตัวอย่างโค้ด

class Solution:
    def solve(self, length, n):
        MOD = 10**9 + 7
        N = length
        def dp(i, jumps):
            if jumps == 0:
                return int(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