记忆化与动态规划 space 复杂度
memoization vs dynamic programming space complexity
我想知道一个问题，比如 LCS，我们可以降低 dp 解决方案的 space 复杂性，因为当我们在 dp 中填充 table 时，我们只使用 dp[i - 1][j]或 dp[i][j - 1] 填充 dp[i][j] 而不是大小为 m X n 的 dp table。
我们可以使用dp[2][n]解决这个问题，并在计算时切换状态。这可以通过记忆将 space 复杂度降低到 O(n + m) 吗？
简单的答案是
没有
在 bottom Up 中，您可以删除不需要的行，因为您知道这些行不会再次使用....
在 Memoization 中，递归以任何顺序调用而不是完整的形式方法，例如：从 LCS(i,j) 调用 LCS(i-1,j) 并计算并保存此结果！现在，递归调用 LCS(k,x)（对于某些其他情况），这会导致相同的子问题 LCS(i-1,j) 现在，如果您删除了这个不会正确记忆解决方案的存储值......！
您不能确定哪个子问题要记忆而不是记忆。
相反，在自下而上我们确定哪些子问题不会被再次使用（这就是我们消除其他行的原因）！
我想知道一个问题，比如 LCS，我们可以降低 dp 解决方案的 space 复杂性，因为当我们在 dp 中填充 table 时，我们只使用 dp[i - 1][j]或 dp[i][j - 1] 填充 dp[i][j] 而不是大小为 m X n 的 dp table。
我们可以使用dp[2][n]解决这个问题，并在计算时切换状态。这可以通过记忆将 space 复杂度降低到 O(n + m) 吗？
简单的答案是 没有
在 bottom Up 中，您可以删除不需要的行，因为您知道这些行不会再次使用.... 在 Memoization 中，递归以任何顺序调用而不是完整的形式方法，例如：从 LCS(i,j) 调用 LCS(i-1,j) 并计算并保存此结果！现在，递归调用 LCS(k,x)（对于某些其他情况），这会导致相同的子问题 LCS(i-1,j) 现在，如果您删除了这个不会正确记忆解决方案的存储值......！
您不能确定哪个子问题要记忆而不是记忆。 相反，在自下而上我们确定哪些子问题不会被再次使用（这就是我们消除其他行的原因）！