Python의 고유 경로

<시간/>

n x m 그리드(n 행 및 m 열)의 왼쪽 상단 모서리에 로봇이 있다고 가정합니다. 로봇은 어느 시점에서든 아래쪽이나 오른쪽으로만 움직일 수 있습니다. 로봇은 그리드의 오른쪽 하단 모서리에 도달하려고 합니다(아래 다이어그램에서 'END로 표시됨). 그렇다면 가능한 고유한 경로가 몇 개나 찾아야 할까요? 예를 들어 m =3이고 n =2이면 그리드는 다음과 같습니다. -

로보
		종료

출력은 3이므로 시작 위치에서 끝 위치까지 도달하는 총 3가지 방법이 있습니다. 이 경로는 -

오른쪽 → 오른쪽 → 아래쪽
오른쪽 → 아래쪽 → 오른쪽
아래쪽 → 오른쪽 → 오른쪽

단계를 살펴보겠습니다 -

이를 해결하기 위해 동적 프로그래밍 접근 방식을 사용할 것입니다.
행 :=n 및 열 :=m, n x m 차수의 테이블 DP를 만들고 -1로 채웁니다.
DP[행 – 2, 열 – 1] :=1
0에서 col
- DP[n – 1, i] :=1
0에서 행까지의 범위에 있는 i의 경우
- DP[i, 열 – 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