C++에서 역 폴란드 표기법 평가

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

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

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

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

단계를 살펴보겠습니다.

• 동적 프로그래밍 접근 방식에서 사용할 하나의 테이블을 만듭니다.
• n :=삼각형의 크기
• i:=n – 2에서 0까지
  • j의 경우 :=0에서 i
    • dp[j] :=삼각형[i, j] + dp[j] 및 dp[j + 1]의 최소값
• 반환 dp[0]

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

예시

class Solution {
   public:
   void printVector(vector <int>& v){
   for(int i = 0; i < v.size(); i++)cout << v[i] << " ";
   cout << endl;
}
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]);
      }
      // printVector(dp);
   }
   return dp[0];
   }
};

입력

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

출력

11