C++のNxNグリッドの最小合計立ち下がりパス

問題の説明

• サイズNxNの整数の行列Aが与えられます。タスクは、Aを通る下降経路の最小合計を見つけることです。
• 立ち下がりパスは、最初の行の任意の要素で始まり、最後の行で終わります。
• 次の各行から1つの要素を選択します。次の行の選択肢は、前の行の列と最大で1つ異なる列にある必要があります

例

If N = 2 and matrix is:
{
   {5, 10},
   {25, 15}
} then output will be 20 as element 5 and 15 are selected

例

#include <bits/stdc++.h>
#define MAX 2
using namespace std;
int getMinSumPath(int matrix[MAX][MAX]) {
   for (int row = MAX - 2; row >= 0; --row) {
      for (int col = 0; col < MAX; ++col) {
         int val = matrix[row + 1][col];
         if (col > 0) {
            val = min(val, matrix[row +1][col - 1]);
         }
         if (col + 1 < MAX) {
            val = min(val, matrix[row +1][col + 1]);
         }
         matrix[row][col] = matrix[row][col] +val;
      }
   }
   int result = INT_MAX;
   for (int i = 0; i < MAX; ++i)
   result = min(result, matrix[0][i]);
   return result;
}
int main() {
   int matrix[MAX][MAX] = {
      {5, 10},
      {25, 15},
   };
   cout << "Minimum sum path = " << getMinSumPath(matrix)
   << endl;
   return 0;
}

上記のプログラムをコンパイルして実行する場合。次の出力を生成します

出力

Minimum sum path = 20