Хамгийн их дундаж утга бүхий зам


Хэцүү байдлын түвшин Easy
Байнга асуудаг Cisco Эпик системүүд Саарал улбар шар SAP лабораторууд Times Интернет
Array Динамик програмчлал матриц

Асуудлын мэдэгдэл

"Хамгийн их дундаж утгатай зам" гэсэн бодлогод танд 2D массив эсвэл бүхэл тоон матриц өгөгдсөн болно гэж заасан байдаг. Одоо та зүүн дээд нүдэнд зогсож байгаа бөгөөд баруун доод хэсэгт хүрэх хэрэгтэй гэж үзье. Зорьсон газраа хүрэхийн тулд та доод, эсвэл зөв чиглэлд явах хэрэгтэй. очих газар гэж бид энд баруун баруун нүдийг хэлнэ. Бидэнд хамгийн их дундаж утгыг өгөх ийм замаар явах хэрэгтэй гэсэн нэг нөхцөл бий.

Жишээ нь

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 руу орох нь дамжиггүй эсвэл хугацааны хязгаараас хэтрэх болно Ийм замыг бий болгох нь цаг хугацааны экспоненциал төвөгтэй байдалд хүргэх болно. Тиймээс цаг хугацааны хувьд асуудлыг шийдвэрлэх. Бид үр дүнтэй шийдлийг олох хэрэгтэй. Гэхдээ бид үүнийг яаж хийж чадах вэ? Бид үүнийг Динамик програмчлал ашиглан хийж болно. Асуудал нь хамгийн их замын нийлбэрийн асуудалтай маш төстэй юм. Энэ асуудалд бид 2D массив дахь хамгийн их замын нийлбэрийг олох хэрэгтэй. Бидний хийх зүйл ч мөн адил, гэхдээ эцэст нь бид дунджийг авах болно.

Тиймээс Динамик програмчлал хандлага. Бид DP матрицын нүд тус бүрийг зүүн дээд булангаас одоогийн нүд рүү эхлүүлэх шаардлагатай бол хүрч болох хамгийн дээд нийлбэрийг зааж өгөх 2D 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] // бусад бүх нүдэнд

P + кодын хамгийн их дундаж утга бүхий код

#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 кодыг хамгийн их дундаж утга

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) Учир нь бид оролтын массивыг дайран өнгөрсөн. Манай АН-ын шилжилт зөвхөн О (1) цаг л үргэлжилсэн.

Сансрын нарийн төвөгтэй байдал

O (N ^ 2) Учир нь бид 2D DP массивыг үүсгэсэн.