최소 경로 합계 문제에서 우리는 "a × b" 매트릭스 음수가 아닌 숫자로 구성됩니다. 당신의 임무는 당신이 찾은 경로에 오는 모든 숫자로 구성된 합계를 최소화하는 경로를 왼쪽 상단에서 오른쪽 하단으로 찾는 것입니다.
참고 : 언제든지 아래 또는 오른쪽으로 만 이동할 수 있습니다.
차례
예
입력
[1,0,2],
[2,0,5],
[1,0,1]
산출
2
설명
길을 따르기 때문에 1→0→0→0→1, 합계를 2로 최소화합니다.
이 이미지는 왼쪽 상단에서 오른쪽 하단으로 도달하는 경로를 보여줍니다.
입력
[1,3,1],
[1,5,1],
[4,2,1]
산출
7
설명
길을 따르기 때문에 1→3→1→1→1, 합계를 7로 최소화합니다.
이 이미지는 왼쪽 상단에서 오른쪽 하단에 도달하는 경로를 보여줍니다.
최소 경로 합계 알고리즘
이제 최소 경로 합계의 문제 설명을 이해했습니다. 많이 논의하지 않고이 문제를 구현하는 데 사용되는 알고리즘으로 이동합니다.
- 입력 값을 정렬.
- 중첩 된 for 루프를 열고 모든 행과 열이 지정된 입력 배열을 순회 할 때까지 실행합니다.
- i = = 0 && j = = 0 인 경우
- 그런 다음 계속하면이 반복을 떠나 다음 반복으로 이동합니다.
- 그렇지 않으면 i = = 0 인 경우
- 그런 다음 어레이 [i] [j] = 어레이 [i] [j] + arr [i] [j-1];
- 그렇지 않으면 j = = 0 인 경우
- arr [i] [j] = arr [i] [j] + arr [i-1] [j];
- 다른
- arr [i] [j] = getMin (arr [i-1] [j] + arr [i] [j], arr [i] [j-1] + arr [i] [j])
- 이 값을 둘 사이의 최소값을 반환하는 getMin 함수에 전달합니다.
- i = = 0 && j = = 0 인 경우
- 반환 array [rows-1] [columns-1];
설명
최소 경로 합계 문제에서 우리의 임무는 경로에 들어오는 모든 정수로 구성된 합계를 최소화하는 행렬에서 해당 경로를 찾는 것이므로 함수가 정의 된 함수는 그 함수에 전달되는 두 개의 값.
이제 중첩 된 for 루프를 시작하고 값 (행 -1)에 도달 할 때까지 외부 루프를 실행하고 열 -1까지 내부 루프에 도달하도록합니다.
단계별 실행
이제 최소 경로 합계 문제를 이해하는 예를 들어 보겠습니다.
입력 : {{1,3,4},
{2,0,2},
{2,0,1}};
지금은
- i = 0, j = 0
부분이 실행되면 계속되고 다음 부분으로 이동합니다.
- i = 0, j = 1
else if (i = = 0)이 실행되고 arr [i] [j] = arr [i] [j] + arr [i] [j-1]
의미 arr [0] [1] = 3 + 1 = 4
- i = 0, j = 2
else if (i = = 0)이 실행되고 arr [i] [j] = arr [i] [j] + arr [i] [j-1]
의미 arr [0] [2] = arr [0] [2] + arr [0] [1] = 4 +1 = 5
- i = 1, j = 0
else if (j = = 0)이 실행되고 arr [i] [j] = arr [i] [j] + arr [i-1] [j]
의미 arr [1] [0] = arr [1] [0] + arr [0] [0] = 2 +1 = 3
- i = 1, j = 1
else 부분이 실행되고 getMin (arr [i-1] [j] + arr [i] [j], arr [i] [j-1] + arr [i] [j]) 함수가 호출됩니다.
및 getMin (arr [0] [1]) + arr [1] [1], arr [1] [0] + arr [1] [1]) = (1 + 2, 3 + 2)
arr [3] [1] => arr [1] [1] = 1에서 가장 작은 값은 3을 반환합니다.
- i = 1, j = 2
else 부분이 실행되고 getMin (arr [i-1] [j] + arr [i] [j], arr [i] [j-1] + arr [i] [j]) 함수가 호출됩니다.
및 getMin (arr [0] [2]) + arr [1] [2], arr [1] [1] + arr [1] [2]) = (5 + 2, 3 + 2)
arr [5] [1] => arr [2] [1] = 2에서 가장 작은 값은 5를 반환합니다.
arr [1] [2] = 5.
- i = 2, j = 0
else if (j = = 0)이 실행되고 arr [i] [j] = arr [i] [j] + arr [i-1] [j]
의미 arr [2] [0] = arr [2] [0] + arr [1] [0] = 2 +2 = 4
arr [2] [2] = 4.
- i = 2, j = 1
else 부분이 실행되고 getMin (arr [i-1] [j] + arr [i] [j], arr [i] [j-1] + arr [i] [j]) 함수가 호출됩니다.
및 getMin (arr [1] [1]) + arr [2] [1], arr [2] [0] + arr [2] [1]) = (3 + 0, 4 + 0)
arr [3] [2] => arr [1] [2] = 1에서 가장 작은 값은 3를 반환합니다.
arr [1] [2] = 3.
- i = 2, j = 2
else 부분이 실행되고 getMin (arr [i-1] [j] + arr [i] [j], arr [i] [j-1] + arr [i] [j]) 함수가 호출됩니다.
및 getMin (arr [1] [2]) + arr [2] [2], arr [2] [1] + arr [2] [2]) = (5 + 1, 3 + 1)
arr [4] [2] => arr [2] [2] = 2에서 가장 작은 값은 5를 반환합니다.
arr [2] [2] = 4.
그리고 그것은 2 인 arr [2] [4]를 반환 할 것이고 이것이 최소 합계 경로를 정의하는 우리의 출력 값입니다.
출력 : 4
최소 경로 합계를위한 C ++ 프로그램
#include<iostream>
using namespace std;
int getMin(int val1, int val2)
{
return val1 < val2 ? val1 : val2;
}
int getMinimumSum(int arr[3][3])
{
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
if(i==0 && j == 0)
{
continue;
}
else if(i==0)
{
arr[i][j] = arr[i][j] + arr[i][j-1];
}
else if(j==0)
{
arr[i][j] = arr[i][j] + arr[i-1][j];
}
else
{
arr[i][j] = getMin(arr[i-1][j]+arr[i][j], arr[i][j-1]+arr[i][j]);
}
}
}
return arr[2][2];
}
int main()
{
int inputArray[3][3] = {{1,3,4},
{2,0,2},
{2,0,1}};
cout<<"Length of minimum path sum: "<<getMinimumSum(inputArray);
return 0;
}
Length of minimum path sum: 4
최소 경로 합계를위한 Java 프로그램
class MinimumPathSum {
private static int getMin(int val1, int val2) {
return val1<val2 ? val1 : val2;
}
private static int getMinimumSum(int[][] arr) {
for (int i = 0; i<arr.length; i++) {
for (int j = 0; j<arr[i].length; j++) {
if (i == 0 && j == 0) {
continue;
} else if (i == 0) {
arr[i][j] = arr[i][j] + arr[i][j - 1];
} else if (j == 0) {
arr[i][j] = arr[i][j] + arr[i - 1][j];
} else {
arr[i][j] = getMin(arr[i - 1][j] + arr[i][j], arr[i][j - 1] + arr[i][j]);
}
}
}
int r = arr.length - 1;
int c = arr[0].length - 1;
return arr[r][c];
}
public static void main(String[] args) {
int[][] inputArray = {{1, 3, 4},
{2, 0, 2},
{2, 0, 1}};
System.out.println("Length of minimum path sum: " + getMinimumSum(inputArray));
}
}
Length of minimum path sum: 4
최소 경로 합계에 대한 복잡성 분석
시간 복잡성
O (m * n) 어디에 "엠" 및 "엔" 최소 경로 합 문제에서 주어진 행렬의 행과 열 수입니다.
공간 복잡성
O (1) 최소 경로 합계에 대한 접근 방식을 구현하는 동안 보조 공간을 사용하지 않기 때문입니다.
