Роҳ бо арзиши максималии миёна  


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Cisco Системаҳои Epic Грей норанҷӣ Лабораторияҳои SAP Интернет Times
тартиботи ҳарбӣ Барномарезии динамикӣ 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 пайдо кунем. Ҳамин чизест, ки мо мехоҳем анҷом диҳем, Аммо дар ниҳоят мо миқдорро мегирем.

ҳамчунин нигаред
Тӯлонитарин пайдоиши такрорӣ

Пас барои Барномарезии динамикӣ наздик шудан. Мо массиви 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

Таҳлили мураккабӣ  

Мураккабии вақт

О (N ^ 2) азбаски мо танҳо аз болои массиви вуруд гузаштем. Ва гузариш дар DP мо танҳо O (1) вақтро дар бар гирифт.

ҳамчунин нигаред
Максимум анбора

Мураккабии фазо

О (N ^ 2) зеро мо як массиви 2D DP офаридаем.