셀이 그 안의 동전 수를 나타내는 2D 행렬이 있다고 가정합니다. 코인을 모으는 두 친구가 있고 시작 시 왼쪽 상단 모서리와 오른쪽 상단 모서리에 배치됩니다. 다음 규칙을 따릅니다.
-
코인 수집가는 셀(i, j)에서 셀(i + 1, j - 1), (i + 1, j) 또는 (i + 1, j + 1)로 이동할 수 있습니다.
-
세포에 도달하면 사용 가능한 모든 동전을 수집하여 세포를 비웁니다.
-
수집가는 한 셀에 머물도록 선택할 수 있지만 모든 셀에 있는 동전은 한 번만 수집할 수 있습니다.
모을 수 있는 최대 코인 수를 찾아야 합니다.
따라서 입력이 다음과 같으면
| 0 | 4 | 1 | 0 |
| 3 | 1 | 4 | 0 |
| 2 | 5 | 1 | 1 |
| 3 | 0 | 0 | 0 |
그러면 출력은 17이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
A :=입력 행렬
-
R :=A의 행 수
-
C :=A의 열 개수
-
dp() 함수를 정의합니다. r, c1, c2가 필요합니다.
-
r이 R과 같으면
-
0 반환
-
-
ans :=A[r, c1] +(c1이 c2와 같지 않으면 1이 아니면 0) * A[r, c2]
-
기본 :=및
-
[c1 − 1, c1, c1 + 1]의 각 nc1에 대해 수행
-
[c2 − 1, c2, c2 + 1]의 각 nc2에 대해 다음을 수행합니다.
-
0 <=nc1
-
ans :=ans의 최대값 및 (base + dp(r + 1, nc1, nc2))
-
-
-
-
반환
-
-
반환 dp(0, 0, C - 1)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution: def solve(self, A): R, C = len(A), len(A[0]) def dp(r, c1, c2): if r == R: return 0 ans = base = A[r][c1] + (c1 != c2) * A[r][c2] for nc1 in [c1 − 1, c1, c1 + 1]: for nc2 in [c2 − 1, c2, c2 + 1]: if 0 <= nc1 < C and 0 <= nc2 < C: ans = max(ans, base + dp(r + 1, nc1, nc2)) return ans return dp(0, 0, C − 1) ob = Solution() print(ob.solve([ [0, 4, 1, 0], [3, 1, 4, 0], [2, 5, 1, 1], [3, 0, 0, 0] ]))
입력
[ [0, 4, 1, 0], [3, 1, 4, 0], [2, 5, 1, 1], [3, 0, 0, 0] ]
출력
17