在數組中計算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 自上而下解決方案可以重新定義爲自下而上,反之亦然。
如果有人能夠提供相同的見解,這將是非常有用的。
在此先感謝。
感謝您的回答。是的,你是非常正確的。我特別看到了自頂向下的備忘錄空間需求比自下而上更多的情況。儘管在大多數情況下,爲什麼這樣做已經很明顯了,因爲*不再需要上述行*,但仍然有一些情況是**不直觀**。你能否進一步解釋同樣的見解?此外,我想知道爲什麼自上而下的方法不能用來獲得這種效用。另請參閱有關LIS問題的解釋。 –
@ShivangBansal原因是遞歸+記憶不知道什麼時候某個特定的數據將不再需要,所以必須全部保留。在自下而上,您可以知道何時完成了一段數據,因爲您已經完成了數據。如果這沒有直觀的意義,我可以寫一篇文章,直到你親自看到它纔會有幫助。 – btilly
對不起,我不能更清楚。 – btilly