程序计算python中n位数字的步进数

假设我们有一个数字n，我们必须找到n个数字的步进数。众所周知，当所有相邻数字的绝对差为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]

为了解决这个问题，我们将遵循以下步骤-

m：= 10 ^ 9 + 7
如果n等于0，则

返回0

如果n与1相同，则

返回10

dp：=大小为10且由值1填充的列表
重复n-1次，

ndp [i]：= dp [i-1] + dp [i + 1]
ndp：=大小为10的列表，填充了值0
ndp [0]：= dp [1]
对于1到8的i
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))

输入值

输出结果