Python中检查我们可以移动k次并返回第一个位置的方法数量的程序

假设我们在n长度列表的位置0，并且每次步行，我们可以向右或向左移动一步（不超过界限），或停留在同一位置。现在，如果我们可以进行正好k步，则必须找出我们可以走多少条独特的路径并返回索引0。如果答案非常大，则将其模1000000007。

因此，如果输入为n = 7 k = 4，则输出将为9，因为操作为-

[向右，向右，向左，向左]，
[向右，向左，向右，向左]，
[停留，停留，停留，停留]，
[向右，向左，停留，停留]，
[停留，停留，向右，向左]，
[向右，停留，停留，向左]，
[向右，停留，向左，停留]，
[停留，向右，向左，停留]，
[停留，向右，停留，向左]，

为了解决这个问题，我们将按照以下步骤进行-

m := 1000000007
N := 长度
定义一个函数dp()。这将需要i，jumps
如果jumps与0相同，则
- 如果i与0相同，则返回true，否则返回false
计数：= dp(i，jumps-1)
如果i≥0，则
- count：= count + dp(i + 1，jumps-1)
如果i≤N-1，则
- count：= count + dp(i – 1，jumps-1)
返回计数
从主方法中执行以下操作：
返回dp(0，n)mod m

让我们看一下以下实现，以便更好地理解-

示例

class Solution:
   def solve(self, length, n):
      MOD = 10 ** 9 + 7
      N = length

      def dp(i, jumps):
         if jumps == 0:
            return +(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))