Đường dẫn tổng tối đa trong ma trận từ trên xuống dưới trong C ++

Tuyên bố vấn đề

Xét một ma trận n * n. Giả sử mỗi ô trong ma trận có một giá trị được gán. Chúng ta chỉ có thể đi từ mỗi ô trong hàng i đến một ô cao hơn theo đường chéo trong hàng i + 1 [tức là từ ô (i, j) đến ô (i ​​+ 1, j-1) và ô (i ​​+ 1, j + 1) chỉ còn]. Tìm đường dẫn từ hàng trên cùng đến hàng dưới cùng theo điều kiện đã nói ở trên sao cho tổng lớn nhất thu được

Ví dụ

If given input is:
{
   {5, 6, 1, 17},
   {-2, 10, 8, -1},
   { 3, -7, -9, 4},
   {12, -4, 2, 2}
}

tổng tối đa là (17 + 8 + 4 + 2) =31

Thuật toán

• Ý tưởng là tìm tổng tối đa hoặc tất cả các đường dẫn bắt đầu với mọi ô của hàng đầu tiên và cuối cùng trả về giá trị tối đa trong tất cả các giá trị trong hàng đầu tiên.

• Chúng tôi sử dụng Lập trình động vì kết quả của nhiều vấn đề phụ cần lặp đi lặp lại

Ví dụ

#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;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra tiếp theo−

Maximum Sum = 31