記憶與動態規劃空間複雜度

Question

我想知道LCS的問題，我們可以減少dp解決方案的空間複雜度，因爲當我們在dp中填充表格時，我們只需使用dp[i - 1][j]或dp[i][j - 1]來填充dp[i][j]而不是有一個尺寸爲m×n的dp表。

我們可以使用dp[2][n]解決這個問題，並在計算時切換狀態狀態。這可以通過記憶將空間複雜度降低到O（n + m）嗎？

Answer 1

簡單的答案是 NO

在自下而上的，只是因爲你知道這些行不會再被使用，你可以去除不必要的行.... 在記憶化，在遞歸調用任何而不是一個完整的正式方法，例如：有一個從LCS（i，j）到LCS（i-1，j）的調用，並且讓這個結果被計算並保存！現在，遞歸調用LCS（k，x）（對於其他一些情況），這會導致相同的子問題LCS（i-1，j）。現在，如果您已經刪除了這個不會正確記憶解決方案的存儲值...！

你不能確定要記憶和不記憶的子問題。 與此相反，我們確定哪些子問題不會再使用（這就是爲什麼我們消除其他行）！