C ++中矩阵从上到下的最大求和路径

问题陈述

考虑一个* n矩阵。假设矩阵中的每个单元都有一个分配的值。我们只能从第i行的每个像元到第i + 1行的对角较高的像元[即从cell(i,j)到cell（i + 1，j-1）和cell（i + 1，j + 1） ） 只要]。遵循上述条件，找到从顶行到底行的路径，以便获得最大和

示例

If given input is:
{
   {5, 6, 1, 17},
   {-2, 10, 8, -1},
   { 3, -7, -9, 4},
   {12, -4, 2, 2}
}

最大和为（17 + 8 + 4 + 2）= 31

算法

• 这个想法是找到最大的总和，或从第一行的每个单元格开始的所有路径，最后返回第一行中所有值的最大值。

• 我们使用动态编程，因为一次又一次地需要解决许多子问题

示例

#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
int getMaxMatrixSum(int mat[SIZE][SIZE], int n){
   if (n == 1) {
      return mat[0][0];
   }
   int dp[n][n];
   int maxSum = INT_MIN, max;
   for (int j = 0; j < n; j++) {
      dp[n - 1][j] = mat[n - 1][j];
   }
   for (int i = n - 2; i >= 0; i--) {
      for (int j = 0; j < n; j++) {
         max = INT_MIN;
         if (((j - 1) >= 0) && (max < dp[i + 1][j - 1])) {
            max = dp[i + 1][j - 1];
         }
         if (((j + 1) < n) && (max < dp[i + 1][j + 1])) {
            max = dp[i + 1][j + 1];
         }
         dp[i][j] = mat[i][j] + max;
      }
   }
   for (int j = 0; j < n; j++) {
      if (maxSum < dp[0][j]) {
         maxSum = dp[0][j];
      }
   }
   return maxSum;
}
int main(){
   int mat[SIZE][SIZE] = {
      {5, 6, 1, 17},
      {-2, 10, 8, -1},
      {3, -7, -9, 4},
      {12, -4, 2, 2}
   };
   int n = 4;
   cout << "Maximum Sum = " << getMaxMatrixSum(mat, n) << endl;
   return 0;
}

输出结果

当您编译并执行上述程序时。它产生以下输出-

Maximum Sum = 31