C++의 최소 낙하 경로 합계

정수 A의 정사각형 배열이 있다고 가정하고 A를 통과하는 낙하 경로의 최소 합을 원합니다. 낙하 경로는 기본적으로 첫 번째 행의 요소에서 시작하여 각 행에서 하나의 요소를 선택하는 경로입니다. 그리고 다음 행의 요소는 이전 행의 열과 최대 1만큼 다른 열에 있어야 합니다. 따라서 행렬이 다음과 같은 경우 -

그러면 출력은 12입니다. 다른 떨어지는 경로가 거의 없습니다. [1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9], [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,9], [3,5,7], [3] ,5,8], [3,5,9], [3,6,8], [3,6,9]이고 가장 작은 합 경로는 [1,4,7]이고 합은 12입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=배열의 크기
• n – 2에서 0까지 범위에 있는 i의 경우
  • 0 ~ n
    범위의 j에 대해
    • j – 1 <0이면 x1 :=inf, 그렇지 않으면 x1 :=matrix[i + 1, j - 1]
    • x2 :=행렬[i + 1, j]
    • j + 1>=n이면 x3 :=inf, 그렇지 않으면 x3 :=matrix[i + 1, j + 1]
    • 행렬[i, j] :=행렬[i, j] + x1, x2, x3의 최소값
• ans :=inf
• 0 ~ n – 1 범위의 i에 대해
  • ans :=ans 및 행렬[0, i]의 최소값
• 반환

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

예

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minFallingPathSum(vector<vector<int>>& a) {
      int n = a.size();
      for(int i =n-2;i>=0;i--){
         for(int j =0;j<n;j++){
            int x1 = j-1<0?INT_MAX:a[i+1][j-1];
            int x2 = a[i+1][j];
            int x3 = j+1>=n?INT_MAX:a[i+1][j+1];
            a[i][j]+= min({x1,x2,x3});
         }
      }
      int ans = INT_MAX;
      for(int i =0;i<n;i++){
         ans = min(ans,a[0][i]);
      }
      return ans;
   }
};
main(){
   vector<vector<int>> v = {{1,2,3},{4,5,6},{7,8,9}};
   Solution ob;
   cout <<(ob.minFallingPathSum(v));
}

입력

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

출력

12