Đường đi trọng số tối đa kết thúc tại bất kỳ phần tử nào của hàng cuối trong ma trận trong C++

Trong bài toán này, chúng ta được cho 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ụ là tạo một chương trình tìm đường đi trọng số tối đa kết thúc tại bất kỳ phần tử nào của hàng cuối trong ma trận. Khi tìm đường đi, duyệt sẽ bắt đầu từ góc trên bên trái (0,0) và các di chuyển hợp lệ là xuống và chéo, không cho phép di chuyển sang trái.

Hãy xem một ví dụ để hiểu bài toá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 –

Tất cả các đường đi có thể sử dụng:
Đường 1: 4+5+6 = 15
Đường 2: 4+8+7 = 19
Đường 3: 4+8+2 = 12
Đường 4: 4+5+7 = 16

Trong số đó, đường đi tốt nhất là đường 2 với trọng số 19.

Vì vậy, một giải pháp có thể là tính tất cả các đường đi và so sánh chúng, nhưng cách tiếp cận này sẽ không hiệu quả khi n là số lớn.

Một giải pháp hiệu quả sẽ sử dụng quy hoạch động vì đây là kiểu bài toán chồng chéo. Bắt đầu từ gốc có n nhánh có thể cung cấp kết quả mong muốn.

Chúng ta sẽ tạo một ma trận lưu trữ trọng số tối đa của các đường đi đã duyệt để đến ô đó trong ma trận.

Sau đó, chúng ta sẽ tìm tổng lớn nhất trong hàng cuối của ma trận và in ra.

Ví dụ

Chương trình giải quyết bài toá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<<"Tổng đường đi tối đa từ ô trên trái đến hàng cuối là : "<<maxCost(mat, N)<<endl;
    return 0;
}

Kết quả

Tổng đường đi tối đa từ ô trên trái đến hàng cuối là : 22