>  기사  >  백엔드 개발  >  그리드의 최대 이동 수

그리드의 최대 이동 수

Linda Hamilton
Linda Hamilton원래의
2024-10-30 13:27:03277검색

2684. 그리드의 최대 이동 수

난이도:

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

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

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

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

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

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

예 1:

Maximum Number of Moves in a Grid

  • 입력: 그리드 = [[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:

Maximum Number of Moves in a Grid

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

제약조건:

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

힌트:

  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. 그리드 내 최대 이동 수



  
  
  설명:

  1. dp 초기화: 각 셀의 최대 이동 수를 저장하기 위해 2D 배열 dp를 생성합니다.
  2. 열 반복: 마지막 두 번째 열부터 첫 번째 열까지 반복하여 다음 열의 인접 셀로 가능한 이동을 기반으로 dp[row][col]을 업데이트합니다.
  3. 최대 이동 수 계산: 마지막으로 dp의 첫 번째 열에 있는 최대값이 결과를 제공합니다.
복잡성 분석:

  • 시간 복잡도: O(m x n) 각 셀을 한 번씩 처리하기 때문입니다.
  • 공간 복잡도: dp 배열의 경우 O(m x n)
이 솔루션은 제약 조건을 고려할 때 효율적이며 제공된 한도 내에서 작동합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서

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

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

  • 링크드인
  • 깃허브

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

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.