C++의 삼각형

삼각형이 있다고 가정합니다. 위에서 아래로의 최소 경로 합을 찾아야 합니다. 각 단계에서 아래 행의 인접한 번호로 이동할 수 있습니다.

예를 들어 다음 삼각형이 다음과 같은 경우

[
      [2],
     [3,4],
    [6,5,7],
   [4,1,8,3]
]

위에서 아래로의 최소 경로 합은 11(2 + 3 + 5 + 1 =11)입니다.

단계를 살펴보겠습니다 -

• 동적 프로그래밍 접근 방식에서 사용할 하나의 테이블을 만듭니다.

• n :=삼각형의 크기

• for i :=n – 2에서 0까지

  • j의 경우 :=0 ~ i

    • dp[j] :=삼각형[i, j] + dp[j] 및 dp[j + 1]의 최소값

• 반환 dp[0]

예시(C++)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minimumTotal(vector<vector<int>>& triangle) {
      vector <int> dp(triangle.back());
      int n = triangle.size();
      for(int i = n - 2; i >= 0; i--){
         for(int j = 0; j <= i; j++){
            dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
         }
      }
      return dp[0];
   }
};
main(){
   Solution ob;
   vector<vector<int> > v = {{2},{3,4},{6,5,7},{4,1,8,3}};
   cout << ob.minimumTotal(v);
}

입력

[[2],[3,4],[6,5,7],[4,1,8,3]]

출력

11