爲什麼我得到超時限？

-5

我越來越超出了提交這個問題的時間限制爲什麼我得到超時限？

問：

讓我們考慮數字的三角形，其中一個號碼出現在第一行，兩個數字出現在二線，三中第三行等。開發一個程序，它將計算出現在從頂部朝向底部的路徑上出現的最大數字總和，以便：

在每個路徑上，下一個數字位於行上下面，更確切地說是直接在下面或下面的和一個地方在右邊;

行數嚴格爲正，但小於100個

所有數字都是O和99之間的正整數

我的代碼：

#include<stdio.h> 
    #include<iostream> 
    #include<algorithm> 
    using namespace std; 
    int trian(int i,int j); 
    long long int n,a[100][100]; 
    int main() 
    { 
     long long int t,i,j,v,k; 
     scanf("%lld",&t); 
     for(i=0;i<t;i++) 
     { 
      scanf("%lld",&n); 
      for(j=0;j<n;j++) 
      { 
       for(k=0;k<j+1;k++) 
       { 
        scanf("%lld",&a[j][k]); 
       } 
      } 
      v=trian(0,0); 
      printf("%lld\n",v); 
     } 
    } 
    int trian(int i,int j) 
    { 
     if(i>=n) 
     return 0; 
     else 
     return (a[i][j]+(std::max(trian(i+1,j),trian(i+1,j+1)))); 
    }

來源

2016-01-30 itsayushbansal

請添加（最小必要）代碼（重現您的問題）以及對問題的描述。 –

加入@DanielJour – itsayushbansal

爲什麼我超越時間限制？

考慮這個三角形（忽略編號）：

1 
2 3

這裏要採取2條可能路徑。讓我們添加一行：

1 
2 3 
4 5 6

的4只能通過直接上方結束的路徑到達，5有兩條路徑可以到達它的6只能從先前結局左上方的路徑到達它。我們現在有4條可能的路徑。另一行：

這是8種可能的路徑。你看到一個模式？讓我們來形容路徑直下7，從1開始：

D = DOWN 
R = DOWN AND RIGHT 

DDD

（單）路徑0：

RRR

由於在每一步你走一排，你只能之間選擇這兩種可能性number of rows - 1倍，從而給你：

2^(number of rows - 1) possible paths

隨着100行，這是很多。你的代碼試圖分別計算每條路徑。假設計算1路徑需要1納秒（這將快得很快），計算它們全部需要多於2 * 10^16年。好， ...

時間超出限制

所以你要知道，你不能僅僅計算每一個可能的路徑，並取最大值。主要的問題是：

1 
2 3 
4 5 6

一個路徑5是1 + 3 + 5，將路徑6是1 + 3 + 6。你的代碼分別計算每條路徑，因此1 + 3將被計算兩次。如果你保存了這個結果，你將擺脫大部分不必要的計算。

你怎麼能存儲這樣的結果？那麼，1 + 3是到達3的路徑的計算，所以將它存儲在那裏。如果一個數字（比如說5）可以通過多條路徑到達會怎樣？

5可以通過1 + 2 + 5或1 + 3 + 5聯繫。

的路徑都經歷了5將給予較高的結果，如果它通過3第一wen't，所以只記得這條道路（並通過2忽略的路徑，現在也沒用）。

因此，作爲一個算法：

對於每一行，開始於行1（不是第一，但第二）：對於每一個條目：計算上述左最大條目（如果可用），並直接以上（如果可用）並將結果+條目的值作爲條目的新值存儲。然後，找到最後一行的最大值。

來源

2016-02-01 18:38:44

非常感謝您的詳細解釋@DanielJour – itsayushbansal

爲什麼我得到超時限？

回答

相關問題