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

輸出

Arnab Chakraborty

更新於：2020年12月2日

99 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習