具有最大平均值的路徑  


難度級別 容易獎學金
經常問 思科 史詩系統 灰色橙色 SAP實驗室 時代互聯網
排列 動態編程 矩陣

問題陳述  

問題“最大平均值的路徑”指出給您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] //在這裡,我從矩陣的第一行開始到最後一行
dp [0] [i] = dp [0] [i-1] + a [0] [i] //這裡,我從矩陣的第一列開始到最後一列
//遞歸關係
dp [i] [j] = max(dp [i-1] [j],dp [i] [j-1])+ a [i] [j] //對於所有其他單元格

具有最大平均值的Path的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

具有最高平均值的Path的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陣列。