Leetcode 문제를 해결하고 꿈의 회사로부터 제안 받기||최소 경로 합계

Leetcode 문제 64: 최소 경로 합계

이 시리즈에서는 친구들과 함께 라이브로 Leetcode 미디엄 문제를 해결할 것입니다. YouTube 채널에서 볼 수 있습니다. 오늘 우리는 문제 Leetcode: 64를 할 것입니다. 최소 경로 합

나에 대해 조금, 과거에 Uber India와 Amazon India에서 제안을 받았고 현재 암스테르담의 Booking.com에서 일하고 있습니다.

알고리즘을 배우게 된 동기

Solve Leetcode Problems and Get Offers From Your Dream Companies

문제 설명

음수가 아닌 숫자로 채워진 m x n 그리드가 주어지면 왼쪽 위에서 오른쪽 아래로 경로를 따라 모든 숫자의 합을 최소화하는 경로를 찾습니다.

Note: You can only move either down or right at any point in time

예 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

예 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

제약:

m == 그리드.길이

n == 격자[i].길이

1 <= m, n <= 200

0 <= 그리드[i][j] <= 100

유튜브 토론

해결책

접근법 1: 무차별 대입

Brute Force 접근 방식에는 재귀가 포함됩니다. 각 요소에 대해 오른쪽과 아래쪽의 두 경로를 고려하고 이 두 경로에서 최소 합계를 찾습니다. 합계를 최소화하기 위해 올바른 단계를 수행해야 하는지 또는 하향 단계를 수행해야 하는지 여부를 지정합니다.

비용(i, j) = 그리드[i][j] + min(비용(i+1, j), 비용(i, j+1))

다음 코드는 이 알고리즘을 구현합니다.

C++ 솔루션

자바 솔루션

복잡성 분석

시간 복잡도는 O(2^(m+n))

시간 복잡도는 O(m+n)

O(n*m) 시간복잡도로 이 문제를 풀 수 있습니다.

아이디어는 각 인덱스(i, j)에 대해 왼쪽 상단에서 인덱스(i, j)까지의 최소 경로를 찾는 것입니다.

첫 번째 행 및 열 대소문자

첫 번째 행에서는 오른쪽으로만 이동할 수 있으므로 첫 번째 행의 인덱스에 도달하기 위한 최소 경로 합계는 왼쪽 상단에서 해당 인덱스까지 모든 요소의 합계입니다.

첫 번째 열의 경우 아래로만 이동할 수 있으므로 첫 번째 행의 인덱스에 도달하기 위해 최소 경로 합계는 왼쪽 상단에서 해당 인덱스까지 모든 요소의 합계입니다.

기타 사례

이제 인덱스(i, j)에 도달하려면 두 가지 옵션이 있습니다.

<올>

인덱스(i-1,j)에서 도달

또는 인덱스 (i, j-1)에서 도달

이 두 인덱스 중 최소값을 선택합니다. 그리드의 나머지 부분에 동일한 직관을 적용하면 왼쪽 상단에서 오른쪽 하단까지의 최소 경로 합계를 찾을 수 있습니다.

C++ 솔루션

자바 솔루션

복잡성 분석

시간 복잡도는 O(n*m)

공간 복잡도는 O(1)

읽어주셔서 감사합니다. 더 많은 LeetCode 문제를 보려면 이 간행물을 팔로우하세요!😃

LeetCode Simplified