在C ++中矩阵的最后一行的任何元素处终止的最大权重路径
在这个问题中，我们得到一个整数n和一个大小为nXn的矩阵，其中包含单元的权重。我们的任务是创建一个程序，以找到在矩阵中最后一行的任何元素处结束的最大权重路径。在找到路径时，遍历将从左上角(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