php - 为动态规划保存状态的算法

Question

这是一个关于使用动态编程在问题中保存状态的问题。

• DP 的每个问题都会保存结果并进一步使用它们来减少计算量。假设我们计算函数值，f(x,y)=290并将其保存在二维数组 $save 中，这样，$save[x][y]=290. 这可以在'f'仅依赖于少量变量时完成（例如，在上面的示例中只有 2 个变量 x 和 y）。但是什么时候可以做'f'取决于说，10或15个变量。制作 10 或 15 维的数组不会节省内存。

• 另一种解决方案可能是我们连接变量的值（假设它们是唯一的）并将它们存储在关联数组中，使用通过连接获得的字符串作为键。但是，串联是一项耗时的操作。因此，我们在内存和时间之间进行了权衡。

如果状态所依赖的变量数量更多，有没有办法存储状态？我认为可能有一些方法可以使用 OOPS 或指针，但我不太能够构建任何东西。有什么建议么？每个想法都受到赞赏，但优先考虑有关“C”或“PHP”的解决方案。我知道'C'不处理关联数组，但我只想要一种算法/方法来保存状态。

Answer 1

1. 在稀疏数据中保存状态通常使用map （关联数组）接口完成。尽管 C 没有内置它 - 互联网上到处都是提供此功能的库。

2. 如果您无论如何都要计算大多数/所有 (x1,...,xk) 值 -map不鼓励使用 a - 它会更慢并且不会节省内存（实际上对于这些情况是相反的）。如果是这种情况 - 多维数组可能是最好的解决方案。

3. 很多时候，在 DP 中，您不需要包含迄今为止所有信息的数组，只需要先前计算的“线”，并覆盖数组。有效 - 对于许多需要 k*N 表的 DP 问题，您实际上只需要大小为 2*N 的表，并迭代地覆盖相同的行。同样的原则适用于我认为的任何维度——如果你需要的只是前一行的数据，而不是所有数据。