그리드의 최대 이동 수

2684. 그리드의 최대 이동 수

난이도:중

주제: 배열, 동적 프로그래밍, 매트릭스

양수 정수로 구성된 0 인덱스

m x n 행렬 그리드가 제공됩니다.

행렬의 첫 번째 열에 있는 모든 셀에서 시작하여 다음과 같은 방법으로 그리드를 탐색할 수 있습니다.

• 셀(행, 열)에서 (행 - 1, 열 1), (행, 열 1) 및 (행 1, 열 1) 셀 중 하나로 이동할 수 있습니다. 이동하려는 셀은 현재 셀의 값보다 엄격히 커야 합니다.

수행할 수 있는 최대동작 횟수를 반환합니다.

예 1:

• 입력: 그리드 = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15] ]
• 출력: 3
• 설명: 셀(0, 0)에서 시작하여 다음과 같이 이동할 수 있습니다.
  • (0, 0) -> (0, 1).
  • (0, 1) -> (1, 2).
  • (1, 2) -> (2, 3). 최대로 할 수 있는 이동 횟수임을 알 수 있습니다.

예 2:

• 입력: 그리드 = [[3,2,4],[2,1,9],[1,1,7]]
• 출력: 0
• 설명: 첫 번째 열의 모든 셀에서 시작하면 어떤 이동도 수행할 수 없습니다.

제약조건:

• m == 그리드.길이
• n == 그리드[i].길이
• 2
• 4 5
• 1 <= 그리드[i][j] <= 10⁶

힌트:

1. 동적 프로그래밍을 사용하여 각 셀에서 수행할 수 있는 최대 이동 수를 찾아보세요.
2. 최종 답은 첫 번째 열의 셀 최대값이 됩니다.

해결책:

동적 프로그래밍(DP)을 사용하여 첫 번째 열의 모든 셀에서 시작하여 각 셀의 최대 이동 횟수를 추적할 수 있습니다. 단계별 접근 방식은 다음과 같습니다.

접근하다:

1. DP 배열 정의: dp[row][col]는 그리드[row][col]에서 시작하여 가능한 최대 이동 수를 나타냅니다. 모든 셀에 대해 0으로 초기화합니다.

2. 그리드 횡단:

   • 마지막 열에서 시작하여 뒤로 첫 번째 열로 이동합니다. col 열의 각 셀에 대해 col-1에 대해 가능한 이동을 계산합니다.
   • 대상 셀의 값이 <인 경우에만 가능한 이동(row - 1, col 1), (row, col 1) 및 (row 1, col 1)을 기반으로 dp[row][col]을 업데이트합니다. 🎜>현재 셀보다 훨씬 더 큽니다.

3. 최대 이동 수 계산:

   dp 테이블을 작성한 후 결과는 dp의 첫 번째 열에 있는 최대값이 됩니다. 이는 첫 번째 열의 모든 셀에서 시작하는 최대 이동 수를 나타냅니다.

4. 최첨단 케이스:

   이동이 불가능한 경우를 처리합니다(예: 모든 경로가 인접 셀의 더 낮거나 같은 값으로 차단되는 경우).

이 솔루션을 PHP로 구현해 보겠습니다:

2684. 그리드 내 최대 이동 수

  
  
  설명:




dp 초기화: 각 셀의 최대 이동 수를 저장하기 위해 2D 배열 dp를 생성합니다.

열 반복: 마지막 두 번째 열부터 첫 번째 열까지 반복하여 다음 열의 인접 셀로 가능한 이동을 기반으로 dp[row][col]을 업데이트합니다.

최대 이동 수 계산: 마지막으로 dp의 첫 번째 열에 있는 최대값이 결과를 제공합니다.



  
  
  복잡성 분석:




시간 복잡도: O(m x n) 각 셀을 한 번씩 처리하기 때문입니다.

공간 복잡도: dp 배열의 경우 O(m x n)


이 솔루션은 제약 조건을 고려할 때 효율적이며 제공된 한도 내에서 작동합니다.



연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 
저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.




링크드인

깃허브



          

            
  

            
        
위 내용은 그리드의 최대 이동 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!