โปรแกรมนับจำนวนก้าวของ n หลักใน python

สมมติว่าเรามีตัวเลข n เราต้องหาจำนวนก้าวของ n หลัก อย่างที่เราทราบกันดีอยู่แล้วว่าจำนวนหนึ่งเรียกว่าสเต็ปปิ้งนัมเบอร์ (stepping number) เมื่อตัวเลขที่อยู่ติดกันทั้งหมดมีผลต่างสัมบูรณ์เท่ากับ 1 ดังนั้นหากตัวเลขคือ 123 จะเป็นจำนวนก้าว แต่ 124 ไม่ใช่ หากคำตอบมีขนาดใหญ่มาก ให้ส่งคืนผลลัพธ์ mod 10^9 + 7

ดังนั้น ถ้าอินพุตเท่ากับ n =2 เอาต์พุตจะเป็น 17 เนื่องจากตัวเลขขั้นบันไดคือ [12, 23, 34, 45, 56, 67, 78, 89, 98, 87, 76, 65, 54, 43, 32, 21, 10]

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

ม :=10^9 + 7
ถ้า n เหมือนกับ 0 แล้ว
- คืน 0
ถ้า n เหมือนกับ 1 แล้ว
- คืน 10
dp :=รายการขนาด 10 ที่เต็มไปด้วยค่า 1
วนซ้ำ n - 1 ครั้ง ทำ
- ndp :=รายการขนาด 10 ที่เต็มไปด้วยค่า 0
- ndp[0] :=dp[1]
- สำหรับผมในช่วง 1 ถึง 8 ทำ
  - ndp[i] :=dp[i - 1] + dp[i + 1]
- ndp[9] :=dp[8]
- dp :=ndp
ผลตอบแทน (ผลรวมของตัวเลขทั้งหมดของ dp[จากดัชนี 1 ถึงจุดสิ้นสุด]) mod m

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

ตัวอย่าง

class Solution:
   def solve(self, n):
      m = (10 ** 9 + 7)
      if n == 0:
         return 0
      if n == 1:
         return 10
      dp = [1] * 10
      for _ in range(n - 1):
         ndp = [0] * 10
         ndp[0] = dp[1]
         for i in range(1, 9):
            ndp[i] = dp[i - 1] + dp[i + 1]
         ndp[9] = dp[8]
         dp = ndp
      return sum(dp[1:]) % m

ob = Solution()
n = 3
print(ob.solve(n))