ให้เมทริกซ์ 2 มิติในปัญหานี้ และเราจำเป็นต้องค้นหาเส้นทางที่มีค่าเฉลี่ยสูงสุด สำหรับเส้นทาง ต้นทางของเราคือเซลล์ซ้ายบนสุด และปลายทางคือเซลล์ขวาล่างสุด เช่น −
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
ในปัญหานี้ เราได้รับอนุญาตให้เคลื่อนที่ไปทางขวาหรือลงเท่านั้น สิ่งนี้ทำให้ปัญหาของเราง่ายขึ้น เนื่องจากเรารู้ว่าเราต้องการ N-1 เพื่อย้ายไปทางขวา และ N-1 เลื่อนลงเพื่อไปยังจุดหมายปลายทางของเรา เป็นเส้นทางที่ถูกต้องที่สั้นที่สุด เพื่อที่เราจะพัฒนาแนวทางของเราโดยการสังเกตเหล่านี้
แนวทางในการหาแนวทางแก้ไข
ในแนวทางนี้ เราจำเป็นต้องใช้โปรแกรมไดนามิกเพื่อคำนวณผลรวมของพาธสูงสุดเมื่อตัวส่วนได้รับการแก้ไข
ตัวอย่าง
รหัส C++ สำหรับแนวทางข้างต้น
#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;
} ผลลัพธ์
5.8
คำอธิบายของโค้ดด้านบน
ในแนวทางข้างต้น เราสังเกตว่าการเคลื่อนไหวสูงสุดที่เราทำมีค่าเท่ากับ (2*n) - 1 โดยที่ n คือลำดับของเมทริกซ์ต้นทุนของเราในขณะนี้ เนื่องจากตอนนี้เรามีตัวส่วนตายตัวแล้ว ดังนั้น เราจำเป็นต้องคำนวณผลรวมของเส้นทางสูงสุด นี่เป็นหนึ่งในปัญหา dp แบบคลาสสิก และเราแก้ไขโดยใช้สิ่งนั้น จากนั้นเราพิมพ์ผลลัพธ์ของเรา
บทสรุป
ในบทช่วยสอนนี้ เราจะแก้ปัญหาเพื่อค้นหาเส้นทางที่มีค่าเฉลี่ยสูงสุด นอกจากนี้เรายังได้เรียนรู้โปรแกรม C ++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ ( Normal) ซึ่งเราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์
