从2D矩阵到1D矩阵的01背包动态优化编程

在许多动态编程问题中，您将逐行构建一个2D表，其中每行仅取决于其紧前面的行。如果是0/1背包问题，则重复发生的次数（来自Wikipedia）如下：

如果w i > w ，则m [i，w] = m [i-1，w]

m [i，w] = max（m [i-1，w]，m [i-1，w-w i ] + v i）否则

注意，当填充第i行时，所有从表中读取的数据仅来自第i-1行；表格中较早的行实际上并未使用。因此，您可以通过仅存储两行来节省2D表中的空间-
紧接的前一行和您要填充的行。您可以通过更加智能的填写方式来进一步将其优化为仅一行表条目。这样可以将空间使用量从O（nW）（O（n）行和O（W）列）减少到O（W）（一两行和O（W）列）。

不过，这是有代价的。许多DP算法并不会在运行时显式计算解决方案，而是填写表格，然后在表格最后进行第二遍 *** 作以恢复最佳答案。如果只存储一行，那么您将获得最佳答案的
值 ，但是您可能不知道最佳答案是什么。在这种情况下，您可以读取可放入背包的最大值，但不一定能够恢复要获得的最大价值。

希望这可以帮助！