최소 경로 합계

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

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

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