Chương trình đếm số bước gồm n chữ số trong python

Giả sử chúng ta có một số n, chúng ta phải tìm số bước của chữ số n. Như chúng ta biết một số được gọi là số bước khi tất cả các chữ số liền kề có hiệu số tuyệt đối là 1. Vì vậy, nếu một số là 123, đây là số bước nhưng 124 thì không. Nếu câu trả lời là rất lớn thì trả về kết quả mod 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là n =2, thì đầu ra sẽ là 17, vì các số bước là [12, 23, 34, 45, 56, 67, 78, 89, 98, 87, 76, 65, 54, 43, 32, 21, 10]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m:=10 ^ 9 + 7
• nếu n giống 0, thì
  • trả về 0
• nếu n giống 1, thì
  • trả lại 10
• dp:=danh sách kích thước 10 chứa đầy giá trị 1
• lặp lại n - 1 lần, thực hiện
  • ndp:=danh sách kích thước 10 chứa đầy giá trị 0
  • ndp [0]:=dp [1]
  • đối với tôi trong phạm vi từ 1 đến 8, hãy thực hiện
    • ndp [i]:=dp [i - 1] + dp [i + 1]
  • ndp [9]:=dp [8]
  • dp:=ndp
• return (tổng tất cả các số của dp [từ chỉ mục 1 đến cuối]) mod m

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

3

Đầu ra

32