在C ++中矩阵的最后一行的任何元素处终止的最大权重路径

在这个问题中，我们得到一个整数n和一个大小为n X n的矩阵，其中包含单元的权重。我们的任务是创建一个程序，以找到在矩阵中最后一行的任何元素处结束的最大权重路径。在找到路径时，遍历将从左上角(0,0)开始，有效的移动将向下且为对角线，不允许向左移动。

让我们举个例子来了解这个问题，

输入-

n = 3
Mat[3][3] ={
   {4, 3, 1}
   {5, 8, 9}
   {6, 7, 2}}

输出 -

19

说明-

All paths that can be used will be
Path1: 4+5+6 = 15
Path2: 4+8+7 = 19
Path3: 4+8+2 = 12
Path4: 4+5+7 = 16

因为其中最好的路径是权重为19的路径2

因此，一种可能的解决方案是计算所有路径，然后将它们进行比较，但是当n个数字较大时，这将是一种低效的方法。

一个有效的解决方案是使用动态编程，因为这是一种重叠的问题。从根开始，它们是可以提供所需结果的n个分支。

我们将创建一个矩阵，该矩阵将存储要遍历以到达矩阵中该单元格的给定路径的最大权重。

我们将这是矩阵最后一行中的最大和并打印出来。

示例

解决问题的程序，

#include<bits/stdc++.h>
using namespace std;
const int MAX = 1000;
int maxCost(int matrix[][MAX], int N) {
   int sumMat[N][N];
   memset(sumMat, 0, sizeof(sumMat));
   int maxSum = 0;
   sumMat[0][0] = matrix[0][0];
   for (int i=1; i<N; i++)
      sumMat[i][0] = matrix[i][0] + sumMat[i-1][0];
   for (int i=1; i<N; i++)
   for (int j=1; j<i+1&&j<N; j++)
      sumMat[i][j] = matrix[i][j] + max(sumMat[i-1][j-1], sumMat[i-1][j]);
   for (int i=0; i<N; i++)
      if (maxSum < sumMat[N-1][i]) maxSum = sumMat[N-1][i];
      return maxSum;
}
int main(){
   int mat[MAX][MAX] ={
      {5 , 6 , 1 },
      {2 , 11 , 10 },
      {15, 3 , 2 }};
   int N = 3;
   cout<<"Maximum Path Sum for top-left cell to last row is : "<<maxCost(mat, N)<<endl;
   return 0;
}

输出结果

Maximum Path Sum for top-left cell to last row is : 22