C++での最小立ち下がりパスの合計

整数Aの正方配列があるとすると、Aを通る立ち下がりパスの最小合計が必要です。立ち下がりパスは、基本的に、最初の行の任意の要素から始まり、各行から1つの要素を選択するパスです。また、次の行の要素は、前の行の列と最大で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：=matrix [i + 1、j]
    • j + 1> =nの場合、x3：=inf、それ以外の場合、x3：=matrix [i + 1、j + 1]
    • matrix [i、j]：=matrix [i、j] + x1、x2、x3の最小値
• ans：=inf
• 0からn–1の範囲のiの場合
  • ans：=ansとmatrix[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