Trong bài toán này, chúng ta được cung cấp một số nguyên n và một ma trận kích thước n X n chứa trọng số của ô. Nhiệm vụ của chúng ta là tạo một chương trình tìm đường dẫn trọng số lớn nhất kết thúc tại bất kỳ phần tử nào của hàng cuối cùng trong ma trận. Trong khi tìm đường, đường đi ngang sẽ bắt đầu từ trên cùng bên trái (0,0) và các bước di chuyển hợp lệ sẽ đi xuống và theo đường chéo, không được phép di chuyển sang trái.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào -
n = 3
Mat[3][3] ={
{4, 3, 1}
{5, 8, 9}
{6, 7, 2}} Đầu ra -
19
Giải thích -
All paths that can be used will be Path1: 4+5+6 = 15 Path2: 4+8+7 = 19 Path3: 4+8+2 = 12 Path4: 4+5+7 = 16
Trong số này, con đường tốt nhất có thể là con đường 2 với trọng số 19
Vì vậy, một giải pháp khả thi có thể là tính toán tất cả các đường dẫn và sau đó so sánh chúng, nhưng đây sẽ là một cách tiếp cận không hiệu quả khi n số lượng lớn.
Một giải pháp hiệu quả sẽ là sử dụng lập trình động vì đây là một dạng bài toán chồng chéo. Bắt đầu từ gốc, chúng có n nhánh có thể cung cấp kết quả mong muốn.
Chúng tôi sẽ tạo một ma trận sẽ lưu trữ trọng số tối đa của các đường dẫn đã cho được duyệt qua để đến ô đó trong ma trận.
Đây là giá trị tổng lớn nhất trong hàng cuối cùng của ma trận và in nó ra.
Ví dụ
Chương trình giải quyết vấn đề,
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1000;
int maxCost(int matrix[][MAX], int N) {
int sumMat[N][N];
memset(sumMat, 0, sizeof(sumMat));
int maxSum = 0;
sumMat[0][0] = matrix[0][0];
for (int i=1; i<N; i++)
sumMat[i][0] = matrix[i][0] + sumMat[i-1][0];
for (int i=1; i<N; i++)
for (int j=1; j<i+1&&j<N; j++)
sumMat[i][j] = matrix[i][j] + max(sumMat[i-1][j-1], sumMat[i-1][j]);
for (int i=0; i<N; i++)
if (maxSum < sumMat[N-1][i]) maxSum = sumMat[N-1][i];
return maxSum;
}
int main(){
int mat[MAX][MAX] ={
{5 , 6 , 1 },
{2 , 11 , 10 },
{15, 3 , 2 }};
int N = 3;
cout<<"Maximum Path Sum for top-left cell to last row is : "<<maxCost(mat, N)<<endl;
return 0;
} Đầu ra
Maximum Path Sum for top-left cell to last row is : 22