Tổng đường dẫn tối đa trong một tam giác Đảo ngược trong C ++

Trong bài toán này, chúng ta được cung cấp các số dưới dạng một tam giác ngược. Nhiệm vụ của chúng tôi là tạo một chương trình tìm tổng đường dẫn tối đa trong một tam giác ngược.

Hình tam giác ngược dạng số là một sự sắp xếp khi hàng đầu tiên chứa n phần tử, hàng thứ hai chứa n-1, v.v.

Ở đây, chúng ta phải tìm tổng lớn nhất có thể đạt được là 3 bằng cách thêm một phần tử từ mỗi hàng.

Hãy lấy một ví dụ để hiểu vấn đề -

Đầu vào -

5 1 9
 3 6
  2

Đầu ra - 17

Giải thích - Ở đây, tôi đã tìm thấy đường dẫn từ hàng cuối cùng đến hàng trên cùng, xem xét các phần tử tối đa có thể có trong đường dẫn.

Để giải quyết vấn đề này, chúng tôi sẽ sử dụng cách tiếp cận lập trình động, tương tự như những gì chúng tôi áp dụng trong trường hợp các vấn đề về đường dẫn chi phí tối thiểu. Ở đây, chúng ta sẽ bắt đầu từ dưới cùng và sau đó tìm đường dẫn mà nó cho tổng lớn nhất.

Trước đó, chúng ta sẽ coi tam giác ngược như một ma trận thông thường bằng cách dịch chuyển tất cả các số sang trái và thêm các số 0 vào các vị trí còn lại.

Ví dụ

Chương trình tìm tổng đường dẫn lớn nhất trong một tam giác ngược -

#include <iostream>
using namespace std;
#define N 3
int findMaxPathSumInvertedTriangle(int matrix[][N]){
   int maxSum = 0;
   for (int i = N - 2; i >= 0; i--) {
      for (int j = 0; j < N - i; j++) {
         if (j - 1 >= 0)
            matrix[i][j] += max(matrix[i + 1][j], matrix[i + 1][j - 1]);
         else
            matrix[i][j] += matrix[i + 1][j];
            maxSum = max(maxSum, matrix[i][j]);
      }
   }
   return maxSum;
}
int main(){
   int invertedTriangle[N][N] = {
      {5, 1, 9},
      {3, 6, 0},
      {2, 0, 0}};
   cout<<"The maximum path sum is "<<findMaxPathSumInvertedTriangle(invertedTriangle);
   return 0;
}

Đầu ra

The maximum path sum is 17