C++LeetCode(120.삼각형)구현

[LeetCode]120.삼각형 삼각형
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
이 문 제 는 우리 에 게 2 차원 배열 로 구 성 된 삼각형 을 주 었 고 우 리 는 위 에서 아래로 의 경 로 를 찾 아 경로 와 최 단 을 찾 게 했다.그렇다면 그 문 제 는 폭력 적 인 해결 을 먼저 고려 해 보 자.우 리 는 모든 경 로 를 옮 겨 다 니 려 면 단계 적 인 시간 복잡 도가 될 수 있다 는 것 을 알 수 있다.OJ 는 반드시 꺼 져 야 한다.빨리 생각 을 끊 는 것 이 좋다.시간 복잡 도 를 최적화 시 켜 야 합 니 다.문제 에서 준 예 는 사람 을 빗 나 가게 하기 쉽 고 탐욕 알고리즘 이 문 제 를 풀 수 있다 고 착각 하 게 합 니 다.문제 의 예 에서 빨간색 배열 을 보면 뿌리 숫자 2 의 아래 에서 작은 숫자 3 을 선택 하고 3 의 아래 에서 작은 숫자 5 를 선택 하 며 5 의 아래 에서 작은 숫자 1 을 선택 하기 때 문 입 니 다.매번 다음 층 과 인접 한 두 숫자 중 작은 숫자 중 하 나 를 선택 하면 됩 니 다.답 을 얻 을 수 있 을 것 같 습 니 다.사실은 옳지 않 습 니 다.탐욕 알고리즘 은 국부 적 으로 가장 작 게 가 져 갈 수 있 지만 매번 전체 국면 에서 가장 작 게 가 져 갈 수 없습니다.다른 분기 의 밑 에 있 는 숫자 가 갑자기 매우 작 아 질 수 있 습 니 다.그러나 탐욕 알고리즘 은 다른 모든 가 지 를 잘 랐 습 니 다.그래서 우리 가 전체 국면 에서 가장 작은 것 을 얻 을 수 있 도록 동적 계획 Dynamic Programming 은 두 가지 선택 이 아 닙 니 다.사실 이 문제 랑...  Dungeon Game  매우 유사 하 다.모두 DP 로 문 제 를 풀 었 다.그러면 사실 우 리 는 dp 배열 을 새로 만 들 지 않 고 triangle 배열 을 직접 재 활용 할 수 있 습 니 다.우 리 는 한 층 한 층 의 누적 을 원 합 니 다.그래서 triangle[i][j]는 맨 윗 층 에서(i,j)위치 까지 의 최소 경로 와 입 니 다.그러면 우 리 는 어떻게 상태 전이 방정식 을 얻 을 수 있 습 니까?사실 어렵 지 않 습 니 다.모든 결점 이 아래로 내 려 갈 수 있 는 것 은 그 와 인접 한 두 개의 숫자 만 있 기 때 문 입 니 다.그러면 모든 위치(i,j)는 상부 에서 그 와 인접 한 두 개의 위치 만 올 수 있 습 니 다.즉,(i-1,j-1)과(i-1,j)두 개의 위치 입 니 다.그러면 상태 이동 방법 은 다음 과 같 습 니 다.
triangle[i][j] = min(triangle[i - 1][j - 1], triangle[i - 1][j])
우 리 는 두 번 째 줄 부터 업 데 이 트 를 시작 합 니 다.양쪽 의 숫자 가 한 줄 의 경계 값 을 직접 부여 하 는 것 을 주의 하 십시오.그러면 마지막 으로 우 리 는 맨 밑 에서 가장 작은 숫자 를 찾 으 면 전체 에서 가장 작은 경로 와 코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        for (int i = 1; i < triangle.size(); ++i) {
            for (int j = 0; j < triangle[i].size(); ++j) {
                if (j == 0) {
                    triangle[i][j] += triangle[i - 1][j];
                } else if (j == triangle[i].size() - 1) {
                    triangle[i][j] += triangle[i - 1][j - 1];
                } else {
                    triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j]);
                }
            }
        }
        return *min_element(triangle.back().begin(), triangle.back().end());
    }
};

이런 방법 은 OJ 를 통과 할 수 있 지만 원시 수조 triangle 을 수 정 했 기 때문에 이상 적 인 방법 은 아니다.인터넷 에서 더 좋 은 DP 방법 을 찾 았 는데,이 방법 은 삼각형 의 마지막 줄 을 복사 하여 업데이트 할 수 있 는 배열 로 삼 았 다.그 다음 에 이 DP 배열 을 하나씩 옮 겨 다 니 며 모든 숫자 에 대해 그 후의 요소 와 비교적 작은 것 을 선택 한 다음 에 한 줄 의 인접 한 위치 에 있 는 요 소 를 새로운 요소 로 한 다음 에 한 층 한 층 위로 스 캔 한다.전체 과정 과 거품 정렬 의 원리 차이 가 많 지 않 고 마지막 에 가장 작은 요 소 는 모두 앞으로 나 왔 다.첫 번 째 요 소 는 바로 원 하 는 것 이다.코드 는 다음 과 같 습 니 다:
해법 2: 

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int> dp(triangle.back());
        for (int i = (int)triangle.size() - 2; i >= 0; --i) {
            for (int j = 0; j <= i; ++j) {
                dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];
            }
        }
        return dp[0];
    }
};

다음은 입력 배열 에 대한 예 를 살 펴 보 겠 습 니 다.
     -1
    2   3
  1  -1  -3
5   3   -1   2
다음은 DP 배열 의 변환 과정 을 살 펴 보 겠 습 니 다.(빨간색 숫자 는 매번 dp 배열 의 중간 값 이 바 뀌 는 위치 입 니 다)
DP：5  3  -1  2
DP：4  3  -1  2
DP：4  -2  -1  2
DP：4  -2  -4  2
DP：0  -2  -4  2
DP：0  -1  -4  2
DP：-2  -1  -4  2
참고 자료:
https://leetcode.com/problems/triangle/
https://leetcode.com/problems/triangle/discuss/38730/DP-Solution-for-Triangle
https://leetcode.com/problems/triangle/discuss/38918/C%2B%2B-top-down-and-bottom-up-solutions.
C++구현 LeetCode(120.삼각형)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 삼각형 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!