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