在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：大小为10的列表，填充值为0
- ndp [0]:= dp [1]
- 对于i在1到8的范围内进行以下操作
  - ndp [i]：= dp [i-1] + dp [i + 1]
- ndp [9]：= dp [8]
- dp：= ndp
返回（从索引1到结尾的所有dp数字的总和）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))