Trong bài toán này, chúng ta đưa ra các số có dạng một tam giá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 lớn nhất trong một tam giác.
Các phần tử được sắp xếp bắt đầu từ hàng đầu tiên với 1 phần tử và sau đó là các hàng tiếp theo với số lượng phần tử tăng dần cho đến khi có phần tử ở hàng thứ n.
Vì vậy, chương trình sẽ tìm đường dẫn cung cấp tổng các phần tử lớn nhất trong tam giác. Vì vậy, chúng ta phải tìm đường dẫn sẽ cung cấp tổng tối đa.
Hãy lấy một ví dụ để hiểu vấn đề -
Đầu vào -
1 5 6 8 2 9
Đầu ra - 16
Giải thích -
Đường dẫn từ trên cùng sẽ trả về tổng lớn nhất - 9 + 6 + 1 =16
Để giải quyết vấn đề này, chúng tôi sẽ sử dụng lập trình động sử dụng cách tiếp cận từ dưới lên.
Đối với điều này, trước tiên chúng ta sẽ chuyển sang trái tất cả các số của tam giác và thêm số 0 vào cuối. Điều này sẽ làm cho tam giác giống như một ma trận tương tự như những gì chúng ta thấy trong bài toán đường dẫn chi phí tối thiểu. Sau đó, chúng ta sẽ bắt đầu từ dưới cùng, và đối với mỗi phần tử, chúng ta sẽ kiểm tra tất cả các đường dẫn có thể có và chọn đường dẫn cung cấp tổng lớn nhất có thể cho đến phần tử đó. Và đi qua đỉnh theo cách tương tự để tìm tổng lớn nhất có thể của đường đi trong tam giác.
Ví dụ
Chương trình tìm tổng đường dẫn lớn nhất trong tam giá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;
} Đầu ra
The maximum path sum in triangle is 16