Tổng đường đi lớn nhất trong tam giá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. Nhiệm vụ là viết chương trình tìm tổng đường đi lớn nhất trong tam giác.

Cấu trúc tam giác

Các phần tử được sắp xếp bắt đầu từ hàng 1 với 1 phần tử, các hàng tiếp theo có số phần tử tăng dần cho đến hàng thứ n.

Ví dụ minh họa

Đầu vào:

  1
 5 6
8 2 9

Đầu ra: 16

Giải thích: Đường đi từ đỉnh cho tổng lớn nhất: 9 + 6 + 1 = 16

Phương pháp giải

Sử dụng quy hoạch động với tiếp cận bottom-up:

1. Dịch chuyển tất cả các số của tam giác sang trái và thêm 0 vào cuối để biến thành ma trận
2. Bắt đầu từ hàng cuối cùng, với mỗi phần tử kiểm tra các đường đi có thể và chọn đường cho tổng lớn nhất
3. Tiếp tục di chuyển lên trên đến đỉnh tam giác

Chương trình C++

#include<iostream> 
using namespace std; 
#define N 3 

int findMaxPathSumTriangle(int mat[][N], int m, int n) {
    for (int i = m - 1; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            if (mat[i + 1][j] > mat[i + 1][j + 1])
                mat[i][j] += mat[i + 1][j];
            else
                mat[i][j] += mat[i + 1][j + 1];
        }
    }
    return mat[0][0];
}

int main() {
    int triangle[N][N] = {
        {1, 0, 0},
        {5, 6, 0},
        {8, 2, 9}
    };
    cout << "The maximum path sum in triangle is " << findMaxPathSumTriangle(triangle, 2, 2);
    return 0;
}

Kết quả

The maximum path sum in triangle is 16