Максималдуу орточо мааниси бар жол


Кыйынчылык деңгээли жеңил
Көп суралган Cisco Epic системасы GreyOrange SAP Labs Times Internet
согуштук тизме Динамикалык программалоо Matrix

Маселени билдирүү

"Максималдуу орточо мааниси бар жол" көйгөйүндө сизге 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] // башка бардык уячалар үчүн

Максималдуу орточо мааниси бар Жол үчүн C ++ коду

#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) анткени биз жөн гана киргизүү массивин басып өттүк. Биздин DPде өтүү O (1) убакытты гана алган.

Космостун татаалдыгы

O (N ^ 2) анткени биз 2D DP массивин түздүк.