เส้นทางที่มีค่าเฉลี่ยสูงสุด


ระดับความยาก สะดวกสบาย
ถามบ่อยใน ซิสโก้ ระบบมหากาพย์ สีเทาOrange SAP Labs ไทม์อินเทอร์เน็ต
แถว การเขียนโปรแกรมแบบไดนามิก มดลูก

คำชี้แจงปัญหา

ปัญหา“ เส้นทางที่มีค่าเฉลี่ยสูงสุด” ระบุว่าคุณได้รับอาร์เรย์ 2 มิติหรือเมทริกซ์ของจำนวนเต็ม ตอนนี้ให้พิจารณาว่าคุณยืนอยู่ที่เซลล์ด้านซ้ายบนและต้องไปถึงด้านล่างขวา ในการไปถึงจุดหมายคุณจะต้องไปตามทิศทางล่างสุดหรือไปในทิศทางที่ถูกต้อง ตามปลายทางในที่นี้เราหมายถึงเซลล์ล่างขวา เงื่อนไขประการหนึ่งคือคุณต้องเดินไปตามเส้นทางดังกล่าวซึ่งทำให้เราได้ค่าเฉลี่ยสูงสุด

ตัวอย่าง

3 3 // number of rows and columns
1 1 2
10 1 100
10 10 1
22.6

คำอธิบาย

เส้นทางที่มีค่าเฉลี่ยสูงสุด

เราย้ายจากเซลล์ด้านซ้ายบนในลักษณะต่อไปนี้: 1-> 10-> 1-> 100-> 1 ดังนั้นการเพิ่มสิ่งนี้ทำให้เราได้ผลรวม 113 ค่าเฉลี่ยจึงเท่ากับ 113/5 = 22.6

เข้าใกล้

หนึ่งสามารถคิดวิธีการบังคับเดรัจฉานซึ่งก็คือการสร้างวิธีที่เป็นไปได้ทั้งหมดในการเข้าถึงเซลล์ล่างขวา เมื่อคุณสร้างเส้นทางทั้งหมดแล้ว ตอนนี้ไปที่พวกเขาและหาผลรวมของจำนวนเต็มที่อยู่บนเส้นทาง ดังนั้นเมื่อคุณมีผลรวมทั้งหมด หาผลรวมที่มีค่าสูงสุดจากสิ่งเหล่านี้

แต่การใช้แนวทางนี้มั่นใจว่าจะเข้าสู่ TLE ไม่เช่นนั้นจะเกินเวลาที่กำหนด เนื่องจากการสร้างเส้นทางดังกล่าวจะนำไปสู่ความซับซ้อนของเวลาแบบเอ็กซ์โพเนนเชียล ดังนั้นเพื่อแก้ปัญหาภายใต้ข้อ จำกัด ด้านเวลา เราต้องหาวิธีแก้ปัญหาที่มีประสิทธิภาพ แต่เราจะทำเช่นนั้นได้อย่างไร? เราสามารถทำได้โดยใช้ Dynamic Programming และปัญหายังคล้ายกับปัญหา Maximum Path Sum เป็นอย่างมาก ในปัญหานั้นเราต้องหาผลรวมพา ธ สูงสุดในอาร์เรย์ 2 มิติ เช่นเดียวกับสิ่งที่เราจะทำ แต่สุดท้ายเราจะหาค่าเฉลี่ย

ดังนั้นสำหรับ การเขียนโปรแกรมแบบไดนามิก แนวทาง เราจะสร้างอาร์เรย์ 2D DP โดยแต่ละเซลล์ในเมทริก DP จะแสดงถึงผลรวมสูงสุดที่สามารถบรรลุได้หากเราต้องการเริ่มจากมุมบนซ้ายไปยังเซลล์ปัจจุบัน ดังนั้นเราจึงสามารถเขียนความสัมพันธ์การเกิดซ้ำทั่วไปได้

// กรณีฐาน
dp [0] [0] = a [0] [0]
dp [i] [0] = dp [i-1] [0] + a [i] [0] // ที่นี่ฉันเริ่มจากแถวที่ 1 จนถึงแถวสุดท้ายของเมทริกซ์
dp [0] [i] = dp [0] [i-1] + a [0] [i] // ที่นี่ฉันเริ่มจากคอลัมน์ที่ 1 จนถึงคอลัมน์สุดท้ายของเมทริกซ์
// ความสัมพันธ์การเกิดซ้ำ
dp [i] [j] = max (dp [i-1] [j], dp [i] [j-1]) + a [i] [j] // สำหรับเซลล์อื่น ๆ ทั้งหมด

รหัส C ++ สำหรับ Path ที่มีค่าเฉลี่ยสูงสุด

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

int main(){
  int n,m; // number of rows and columns in input matrix
  cin>>n>>m;

  int input[n][m];
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++)
      cin>>input[i][j];
  }

  int dp[n][m];
  dp[0][0] = input[0][0];
  for(int i=1;i<n;i++)
    dp[i][0] = dp[i-1][0] + input[i][0];
  for(int i=1;i<m;i++)
    dp[0][i] = dp[0][i-1] + input[0][i];

  for(int i=1;i<n;i++){
    for(int j=1;j<m;j++)
      dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + input[i][j];
  }

  // division by n+m-1, because you need to travel at least n+m-1 cells to reach bottom right cell
  cout<<(dp[n-1][m-1]/((double)n+m-1));
}
3 3
1 1 2
10 1 100
10 10 1
22.6

โค้ด Java สำหรับ Path ที่มีค่าเฉลี่ยสูงสุด

import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt(); int m = sc.nextInt(); // number of rows and columns in input matrix

    int input[][] = new int[n][m];
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++)
        input[i][j] = sc.nextInt();
    }

    int dp[][] = new int[n][m];
    dp[0][0] = input[0][0];
    for(int i=1;i<n;i++)
      dp[i][0] = dp[i-1][0] + input[i][0];
    for(int i=1;i<m;i++)
      dp[0][i] = dp[0][i-1] + input[0][i];

    for(int i=1;i<n;i++){
      for(int j=1;j<m;j++)
        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + input[i][j];
    }

    // division by n+m-1, because you need to travel at least n+m-1 cells to reach bottom right cell
    System.out.print(dp[n-1][m-1]/((double)n+m-1));
  }
}
3 3
1 1 2
10 1 100
10 10 1
22.6

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

O (N ^ 2) เนื่องจากเราได้ข้ามผ่านอาร์เรย์อินพุต และการเปลี่ยนแปลงใน DP ของเราใช้เวลาเพียง O (1) ครั้ง

ความซับซ้อนของอวกาศ

O (N ^ 2) ตั้งแต่เราสร้างอาร์เรย์ 2D DP