Pythonの一意のパス

n x mグリッド（n行m列）の左上隅にロボットがあるとします。ロボットは、どの時点でも下側または右側のどちらかにしか移動できません。ロボットは、グリッドの右下隅に到達しようとしています（下の図で「END」とマークされています）。では、可能な一意のパスがいくつあるかを見つける必要がありますか？たとえば、m=3およびn=2の場合、グリッドは次のようになります-

出力は3になるので、開始位置から終了位置に到達する方法は全部で3つあります。これらのパスは-

1. 右→右→下
2. 右→下→右
3. 下→右→右

手順を見てみましょう-

• これを解決するために動的計画法アプローチを使用します
• row：=nおよびcol：=mとし、次数n x mのテーブルDPを作成し、これに-1を入力します
• DP [row – 2、col-1]：=1
• 0からcolの範囲のiの場合
  • DP [n – 1、i]：=1
• 0から行の範囲のiの場合
  • DP [i、col – 1]：=1
• 行-2から-1までの範囲のiの場合
  • 列-2から-1までの範囲のjの場合
    • DP [i、j]：=DP [i + 1、j] + DP [i、j + 1]
• DP [0、0]を返す

理解を深めるために、次の実装を見てみましょう-

例

class Solution(object):
   def uniquePaths(self, m, n):
      row = n
      column = m
      dp = [[-1 for i in range(m)] for j in range(n)]
      dp[row-2][column-1] = 1
      for i in range(column):
         dp[n-1][i] = 1
      for i in range(row):
         dp[i][column-1]=1
      for i in range(row-2,-1,-1):
         for j in range(column-2,-1,-1):
            dp[i][j] = dp[i+1][j] + dp[i][j+1]
      return dp[0][0]
ob1 = Solution()
print(ob1.uniquePaths(10,3))

入力

10
3

出力

55