C++ Đường đi giá trị trung bình lớn nhất trong ma trận

Cho ma trận 2D, tìm đường đi từ góc trên trái đến góc dưới phải (chỉ đi phải hoặc xuống) có giá trị trung bình lớn nhất. Ví dụ:

Input: Matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: 5.8
Đường đi: 1→4→7→8→9, tổng=29, trung bình=29/5=5.8

Số bước cố định = 2n-1. Do đó tối ưu hóa tổng đường đi (dynamic programming).

Phương pháp giải

DP: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + cost[i][j]. Kết quả = dp[n-1][n-1] / (2n-1).

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

int maximumPathSum(int cost[][3], int n) {
    int dp[n+1][n+1];
    dp[0][0] = cost[0][0];
    for (int i=1; i<n; i++) dp[i][0] = dp[i-1][0] + cost[i][0];
    for (int j=1; j<n; j++) dp[0][j] = dp[0][j-1] + cost[0][j];
    for (int i=1; i<n; i++)
        for (int j=1; j<=n; j++)
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + cost[i][j];
    return dp[n-1][n-1];
}

int main() {
    int cost[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
    int n = 3;
    printf("%.1f", float(maximumPathSum(cost, n)) / float(2*n-1));
    return 0;
}

Kết quả

5.8

Giải thích

Mẫu số cố định (2n-1), chỉ cần tìm tổng lớn nhất bằng DP kinh điển. Kết quả chia cho số bước.

Kết luận

Đã giải bài toán đường đi trung bình lớn nhất bằng DP tìm tổng lớn nhất. Code C++ áp dụng cho các ngôn ngữ khác. Hy vọng hữu ích.