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のpath2です

したがって、考えられる解決策の1つは、すべてのパスを計算してからそれらを比較することですが、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