파이썬에서 왼쪽 위 지점에서 오른쪽 아래 지점까지 도달할 수 있는 방법의 수를 찾는 프로그램

<시간/>

하나의 N x M 이진 행렬이 있다고 가정합니다. 여기서 0은 빈 셀을 의미하고 1은 차단된 셀을 의미합니다. 이제 왼쪽 상단 모서리부터 시작하여 오른쪽 하단 모서리에 도달하는 방법의 수를 찾아야 합니다. 답이 매우 크면 10^9 + 7로 수정하십시오.

따라서 입력이 다음과 같으면

0	0	1
0	0	0
1	1	0

그러면 출력은 2가 됩니다. 오른쪽 아래로 이동하는 두 가지 방법이 있습니다:[오른쪽, 아래쪽, 오른쪽, 아래쪽] 및 [아래쪽, 오른쪽, 오른쪽, 아래쪽].

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

dp :=주어진 행렬과 같은 크기의 행렬이고 0으로 채움
dp[0, 0] :=1
행렬의 행 수까지 범위 1에 있는 i에 대해 다음을 수행합니다.
- 행렬[i, 0]이 1과 같으면
  - 루프에서 나오다
- 그렇지 않으면
  - dp[i, 0] :=1
행렬의 열 개수에 대한 범위 1의 j에 대해 다음을 수행합니다.
- 행렬[0, j]가 1과 같으면
  - 루프에서 나오다
- 그렇지 않으면
  - dp[0, j] :=1
행렬의 행 수까지 범위 1에 있는 i에 대해 다음을 수행합니다.
- 행렬의 열 개수에 대한 범위 1의 j에 대해 다음을 수행합니다.
  - 행렬[i,j]가 1과 같으면
    - dp[i, j] :=0
  - 그렇지 않으면
    - dp[i, j] :=dp[i - 1, j] + dp[i, j - 1]
dp의 오른쪽 하단 값을 반환

예제(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

class Solution:
   def solve(self, matrix):
      dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
      dp[0][0] = 1
      for i in range(1, len(matrix)):
         if matrix[i][0] == 1:
            break
         else:
            dp[i][0] = 1
      for j in range(1, len(matrix[0])):
         if matrix[0][j] == 1:
            break
         else:
            dp[0][j] = 1
      for i in range(1, len(matrix)):
         for j in range(1, len(matrix[0])):
            if matrix[i][j] == 1:
               dp[i][j] = 0
            else:
               dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
      return dp[-1][-1]
ob = Solution()
matrix = [
   [0, 0, 1],
   [0, 0, 0],
   [1, 1, 0]
]
print(ob.solve(matrix))

입력

matrix = [
[0, 0, 1],
[0, 0, 0],
[1, 1, 0] ]