Tổng đường đi lớn nhất trong tam giác ngược trong C++

Trong bài toán này, chúng ta được cho các số được sắp xếp dưới dạng tam giác ngược. Nhiệm vụ là viết chương trình tìm tổng đường đi lớn nhất trong tam giác ngược.

Khái niệm tam giác ngược

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

Chúng ta cần tìm tổng lớn nhất có thể đạt được bằng cách chọn một phần tử từ mỗi hàng.

Ví dụ minh họa

Đầu vào:

5 1 9
3 6
2

Đầu ra: 17

Giải thích: Đường đi từ hàng cuối lên hàng đầu tiên cho tổng lớn nhất.

Phương pháp giải

Sử dụng quy hoạch động (dynamic programming) với tiếp cận bottom-up (từ dưới lên), tương tự bài toán tìm đường đi chi phí nhỏ nhất. Cụ thể:

1. Biến tam giác ngược thành ma trận thông thường bằng cách dịch chuyển các số sang trái và bổ sung 0 vào các vị trí còn lại
2. Bắt đầu từ hàng cuối cùng, tính toán tổng lớn nhất có thể đạt được tại mỗi vị trí
3. Di chuyển lên trên từng hàng cho đến đỉnh tam giác

Chương trình 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;
}

Kết quả

The maximum path sum is 17