C ++中NxN网格中的最小求和下降路径

问题陈述

• 给定大小为NxN的整数的矩阵A。任务是找到通过A的下降路径的最小和。

• 下降路径将从第一行中的任何元素开始，到最后一行结束。

• 它从下一行中选择一个元素。下一行的选择必须位于与上一行的列最多相差一列的列中

示例

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