왼쪽 상단에서 오른쪽 하단 셀로 선택하고 Python에서 반환할 수 있는 동전의 수를 찾는 프로그램

가능한 값이 3개인 2D 행렬이 있다고 가정합니다. −

빈 셀의 경우 0입니다.
1코인입니다.
벽의 경우 -1입니다.

왼쪽 위 셀에서 시작하여 오른쪽 또는 아래쪽 방향으로만 이동하여 오른쪽 아래 셀에 도달하여 얻을 수 있는 최대 동전 수를 찾아야 합니다. 그런 다음 위쪽 또는 왼쪽 방향으로만 이동하여 왼쪽 위 셀로 돌아갑니다. 동전을 집었을 때 셀 값은 0이 됩니다. 오른쪽 하단 셀에 도달할 수 없으면 0을 반환합니다.

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

0	1	1
1	1	1
−1	1	1
0	1	1

그러면 출력은 8이 됩니다.

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

n :=매트의 행 개수, m :=매트의 열 개수
util() 함수를 정의합니다. i, j, k, l
i와 j가 mat의 범위에 있지 않거나 mat[i, j]가 −1과 같으면
- 반환 -inf
k와 l이 mat의 범위에 있지 않거나 mat[k, l]이 −1과 같으면
- 반환 -inf
i, j, k 및 l이 모두 0이면
- 반환 매트[0, 0]
최고 :=-inf
[(−1, 0) ,(0, −1) ]의 각 쌍(dx1, dy1)에 대해
- [(−1, 0) ,(0, −1) ]의 각 쌍(dx2, dy2)에 대해
  - best :=best와 util(i + dy1, j + dx1, k + dy2, l + dx2)의 최대값
반환 mat[i, j] +(i가 k와 같지 않으면 1, 그렇지 않으면 0) * mat[k, l] + best
주요 방법에서 다음을 수행하십시오 -
0과 util(n − 1, m − 1, n − 1, m − 1)의 최대값을 반환

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

예

class Solution:
   def solve(self, mat):
      n, m = len(mat), len(mat[0])
      def util(i, j, k, l):
         if not (0 <= i < n and 0 <= j < m) or mat[i][j] == −1:
            return −1e9
         if not (0 <= k < n and 0 <= l < m) or mat[k][l] == −1:
            return −1e9
         if i == 0 and j == 0 and k == 0 and l == 0:
            return mat[0][0]
         best = −1e9
         for dx1, dy1 in [(−1, 0), (0, −1)]:
            for dx2, dy2 in [(−1, 0), (0, −1)]:
               best = max(best, util(i + dy1, j + dx1, k + dy2, l + dx2))
         return mat[i][j] + (i != k) * mat[k][l] + best
      return max(0, util(n − 1, m − 1, n − 1, m − 1))
ob = Solution()
matrix = [
   [0, 1, 1],
   [1, 1, 1],
   [1, −1, 1],
   [0, 1, 1]
]
print(ob.solve(matrix))

입력

[
   [0, 1, 1],
   [1, 1, 1],
   [1, −1, 1],
   [0, 1, 1]
]