최소 경로 합계

난이도 중급
자주 묻는 질문 아마존 블룸버그 게시물에서 Facebook 골드만 삭스 구글 Microsoft
배열 동적 프로그래밍조회수 37

최소 경로 합계 문제에서 우리는 "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로 최소화합니다.

최소 경로 합계

이 이미지는 왼쪽 상단에서 오른쪽 하단에 도달하는 경로를 보여줍니다.

최소 경로 합계 알고리즘

이제 최소 경로 합계의 문제 설명을 이해했습니다. 많이 논의하지 않고이 문제를 구현하는 데 사용되는 알고리즘으로 이동합니다.

  1. 입력 값을 정렬.
  2. 중첩 된 for 루프를 열고 모든 행과 열이 지정된 입력 배열을 순회 할 때까지 실행합니다.
    1. i = = 0 && j = = 0 인 경우
      • 그런 다음 계속하면이 반복을 떠나 다음 반복으로 이동합니다.
    2. 그렇지 않으면 i = = 0 인 경우
      • 그런 다음 어레이 [i] [j] = 어레이 [i] [j] + arr [i] [j-1];
    3. 그렇지 않으면 j = = 0 인 경우
      • arr [i] [j] = arr [i] [j] + arr [i-1] [j];
    4. 다른
      • arr [i] [j] = getMin (arr [i-1] [j] + arr [i] [j], arr [i] [j-1] + arr [i] [j])
    5. 이 값을 둘 사이의 최소값을 반환하는 getMin 함수에 전달합니다.
  3. 반환 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) 최소 경로 합계에 대한 접근 방식을 구현하는 동안 보조 공간을 사용하지 않기 때문입니다.

참조

Translate »