Python에서 수집할 수 있는 최대 동전 수를 찾는 프로그램

각 셀이 일부 동전을 저장하는 2D 행렬이 있다고 가정합니다. [0,0]에서 시작하여 오른쪽이나 아래쪽으로만 이동할 수 있는 경우 오른쪽 하단 모서리에서 수집할 수 있는 최대 동전 수를 찾아야 합니다.

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

경로를 선택하면 출력은 14가 됩니다. [1, 4, 2, 2, 5]

이 문제를 해결하기 위해 다음 단계를 따르겠습니다-

• 범위 1에서 A의 행 수까지 r에 대해 수행

  • A[r, 0] :=A[r, 0] + A[r-1, 0]

• 범위 1의 c에서 A의 열 수까지 수행하려면

  • A[0, c] :=A[0, c] + A[0, c-1]

  • 범위 1에서 A 크기까지의 r에 대해 다음을 수행하십시오.

  • 범위 1에서 A[0] 크기의 c에 대해

  • A[r, c] =A[r, c] + (A[r-1, c] 및 A[r, c-1]의 최대값

• A

  오른쪽 하단의 반환 값

더 나은 이해를 위해 다음 구현을 살펴보겠습니다-

예

class Solution:
   def solve(self, A):
      for r in range(1, len(A)):
         A[r][0] += A[r-1][0]
      for c in range(1, len(A[0])):
         A[0][c] += A[0][c-1]
      for r in range(1, len(A)):
         for c in range(1, len(A[0])):
            A[r][c] += max(A[r-1][c], A[r][c-1])
      return A[-1][-1]
ob = Solution()
matrix = [ [1, 4, 2, 2], [6, 0, 0, 5] ]
print(ob.solve(matrix))

입력

matrix = [
   [1, 4, 2, 2],
   [6, 0, 0, 5]
]

출력

14