如何降低複雜度？

Question

我必須使用動態編程來解決問題。

for(int i = 3; i < N; i++){ 
    for(int j= 3; j < T; j++){ 
    .. 

我想降低複雜性。我該如何做到這一點？

Answer 1

我需要了解你的遞歸的基本情況是什麼。我認爲利用這些信息我可以把它變成一個更有效的循環結構。但以我現在知道了，我也只是抄寫你的第一個功能性定義爲它的邏輯C＃相當於...

int S(int i, int j) 
{ 
    if (?) // the base case, must be at least one, can have more then one. (e.g. when i=N or j=T) 
     return ?; // What gets returned ultimately controls how efficient we can make this. 

    var maxValue = S(i-1, j-1); 
    for (var k = j-2; k < i-3; k++) 
     maxValue = Math.Max(maxValue, S(k, j-3)); 
    return maxValue; 
} 

而且裏面的for循環中，我們可以使事情更加有效的做自己的比較，而不是調用Math.Max。我使用Math.Max很簡單，因爲它更易於閱讀，但簡單的性能增強將是將S的返回放置到一個臨時變量中，然後使用>？：設置maxValue。