Cho một ma trận 2 D trong bài toán này, và chúng ta cần tìm các đường đi có giá trị trung bình lớn nhất. Đối với đường dẫn, nguồn của chúng ta là ô trên cùng bên trái và đích là ô dưới cùng bên phải, chẳng hạn -
Input : Matrix = [1, 2, 3 4, 5, 6 7, 8, 9] Output : 5.8 Path with maximum average is, 1 -> 4 -> 7 -> 8 -> 9 Sum of the path is 29 and average is 29/5 = 5.8
Trong bài toán này, chúng ta chỉ được phép di chuyển sang phải hoặc xuống dưới. Điều này làm cho vấn đề của chúng ta dễ dàng hơn vì chúng ta biết rằng chúng ta cần N-1 để di chuyển sang bên phải và N-1 di chuyển xuống để đến đích. Đó là con đường hợp lệ ngắn nhất để chúng tôi phát triển cách tiếp cận của mình bằng những quan sát này.
Phương pháp tiếp cận để tìm giải pháp
Trong cách tiếp cận này, chúng ta cần áp dụng lập trình động để tính tổng đường dẫn tối đa khi mẫu số được cố định.
Ví dụ
Mã C ++ cho phương pháp tiếp cận trên
#include <bits/stdc++.h>
using namespace std;
int maximumPathSum(int cost[][3], int n){ // our function that return maximum average
int dp[n+1][n+1];
dp[0][0] = cost[0][0];
for (int i = 1; i < n; i++) // initializing the first column of our dp matrix
dp[i][0] = dp[i-1][0] + cost[i][0];
for (int j = 1; j < n; j++) // initializing the first row of our dp matrix
dp[0][j] = dp[0][j-1] + cost[0][j];
for (int i = 1; i < n; i++) // constructing the rest of our matrix
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]; // now we divide the maximum path sum with the number of moves
}
int main(){
int cost[3][3] = { {1, 2, 3}, {4, 5, 6},{7, 8, 9}};// given grid
int n = 3; // order of our matrix
printf("%.1f", float(maximumPathSum(cost, n)) / float((2*n-1)));
return 0;
} Đầu ra
5.8
Giải thích về Quy tắc trên
Trong cách tiếp cận trên, chúng tôi quan sát thấy rằng các bước di chuyển tối đa mà chúng tôi thực hiện bằng (2 * n) - 1, trong đó n là bậc của ma trận chi phí của chúng tôi bây giờ vì chúng tôi hiện có một mẫu số cố định. Do đó, chúng ta cần tính tổng đường dẫn tối đa. Bây giờ, đây là một trong những vấn đề dp cổ điển và chúng tôi giải quyết nó bằng cách sử dụng nó, sau đó chúng tôi in kết quả của chúng tôi.
Kết luận
Trong hướng dẫn này, chúng tôi giải quyết một vấn đề để tìm Đường dẫn có giá trị trung bình lớn nhất. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.