Python程序：检查以k步返回起始位置的方法数量

假设我们位于长度为n的列表的第0个位置，每一步我们可以向右移动一个位置，向左移动一个位置（不超过边界），或停留在同一位置。如果我们可以精确地走k步，那么我们必须找到可以走多少条独特的路径并返回索引0。如果答案非常大，则返回它模10^9 + 7。

因此，如果输入类似于n = 7 k = 4，则输出将为9，因为操作为：

  • [右，右，左，左],
  • [右，左，右，左],
  • [停，停，停，停],
  • [右，左，停，停],
  • [停，停，右，左],
  • [右，停，停，左],
  • [右，停，左，停],
  • [停，右，左，停],
  • [停，右，停，左],

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

  • m := 10^9 + 7
  • N := 列表长度
  • 定义一个函数dp()。这将接收i和jumps作为参数。
  • 如果jumps等于0，则
    • 返回（当i等于0时为真，否则为假）
  • count := dp(i, jumps - 1)
  • 如果i >= 0，则
    • count := count + dp(i + 1, jumps - 1)
  • 如果i <= N - 1，则
    • count := count + dp(i - 1, jumps - 1)
  • 返回count
  • 在主方法中执行以下操作：
  • 返回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))

输入

7, 4

输出

9

更新于：2020年12月2日

99 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告