一維增長子序列的遞歸解決方案中的一次記憶

在數組中計算LIS（最長增加子序列）是一個非常着名的動態規劃問題。然而，在每個教程中，他們首先展示遞歸解決方案，而不使用DP的概念，然後通過應用Bottom-Up DP（迭代解決方案）來解決它。一維增長子序列的遞歸解決方案中的一次記憶

我的問題是：

我們將如何在遞歸解決方案本身使用記憶化。不只是記憶，而是使用一維數組進行記憶。

我做了一些研究，但找不到任何相關的東西。雖然有2個地方已經被要求遞歸記憶1 & 2但在那裏的解決方案是使用二維地圖/數組進行記憶。

無論如何記憶與1D陣列的解決方案，是給錯誤輸出。這裏是我做過什麼：

int lis(int idx, int prev) 
{ 
    if(idx >= N) 
     return 0; 

    if(dp[idx]) 
     return dp[idx]; 

    int best_ans = lis(idx+1, prev); 

    int cur_ans = 0; 
    if(arr[idx] > prev) 
    { 
     cur_ans = 1 + lis(idx+1, arr[idx]); 
    } 
    int ans = max(best_ans, cur_ans); 
    dp[idx] = ans; 
    return ans; 
} 

int main() 
{ 
    // Scan N 
    // Scan arr 

    ans = lis(0, -1)); 
    print ans; 
}

雖然我知道爲什麼這個解決方案是給錯誤輸出的原因：

可以有基於什麼是捐贈指數不止一個解決方案先前的值。

但我仍然想知道如何使用一維數組來完成。

我很好奇，想知道解決的辦法，因爲我已閱讀，每個DP 自上而下解決方案可以重新定義爲自下而上，反之亦然。

如果有人能夠提供相同的見解，這將是非常有用的。

在此先感謝。

來源

2017-02-20 Shivang Bansal

這是無法完成的，因爲問題從根本上需要2D數據結構來解決。

自底向上的方法可以通過在數據結構中生成一行來作弊。隨着時間的推移，它會產生一個二維數據結構，但是在任何時候你只能看到它的一個維度。

自頂向下的方法必須構建整個2D數據結構。

這是DP的基本權衡。寫下自上而下的方法通常更容易。但是自下而上的方法在任何時候都必須具有部分整體數據結構，因此具有顯着更低的內存需求。

來源

2017-02-20 18:53:52 btilly

感謝您的回答。是的，你是非常正確的。我特別看到了自頂向下的備忘錄空間需求比自下而上更多的情況。儘管在大多數情況下，爲什麼這樣做已經很明顯了，因爲*不再需要上述行*，但仍然有一些情況是**不直觀**。你能否進一步解釋同樣的見解？此外，我想知道爲什麼自上而下的方法不能用來獲得這種效用。另請參閱有關LIS問題的解釋。 –

@ShivangBansal原因是遞歸+記憶不知道什麼時候某個特定的數據將不再需要，所以必須全部保留。在自下而上，您可以知道何時完成了一段數據，因爲您已經完成了數據。如果這沒有直觀的意義，我可以寫一篇文章，直到你親自看到它纔會有幫助。 – btilly

對不起，我不能更清楚。 – btilly

一維增長子序列的遞歸解決方案中的一次記憶

回答

相關問題