k回移動してPythonで1位に戻る方法の数を確認するプログラム

n長さリストの位置0にいて、各ステップで、右に1か所または左に1か所（境界を超えない）移動するか、同じ位置にとどまることができるとします。ここで、正確にkステップを実行できる場合は、実行できる一意のウォークの数を見つけて、インデックス0に戻る必要があります。答えが非常に大きい場合は、mod 10 ^ 9+7を返します。

したがって、入力がn =7 k =4の場合、アクションは次のようになり、出力は9になります-

• [右、右、左、左]、
• [右、左、右、左]、
• [Stay、Stay、Stay、Stay]、
• [右、左、滞在、滞在]、
• [滞在、滞在、右、左]、
• [右、滞在、滞在、左]、
• [右、滞在、左、滞在]、
• [滞在、右、左、滞在]、
• [滞在、右、滞在、左]、

これを解決するには、次の手順に従います-

• m：=10 ^ 9 + 7
• N：=長さ
• 関数dp（）を定義します。これには私がかかります、ジャンプ
• ジャンプが0と同じ場合、
  • return（iが0と同じ場合はtrue、それ以外の場合はfalse）
• count：=dp（i、jumps-1）
• i> =0の場合、
  • count：=count + dp（i + 1、jumps-1）
• i <=N-1の場合、
  • count：=count + dp（i-1、jumps-1）
• 返品数
• メインの方法から次の手順を実行します。
• return 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