数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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
因为在这些路径中，最佳路径是路径 2，权重为 19
因此，一种可能的解决方案是计算所有路径，然后进行比较，但是当 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
更新于: 2020年6月3日
298 次浏览
广告