动态规划近似

Question

我正在尝试使用动态编程来计算函数F(x，y)。在功能上：

F(X，Y) = a1 F(X-1，Y)+ a2 F(X-2，Y) ... + ak F(X-k，Y) + b1 F(X，Y-1)+ b2 F(X，Y-2) ... + bk F(X，Y-k)

其中k是一个小数字(k=10)。

问题是，X=1,000,000和Y=1,000,000。因此，计算x=1..1000000和y=1..1000000之间的每个值的F(x，y)是不可行的。是否存在DP的近似版本，其中我可以避免计算大量输入的F(x，Y)，而仍然可以得到F(X，y)的准确估计。

一个类似的例子是字符串匹配算法(Levenshtein的距离)，用于两个非常长和相似的字符串(例如，相似的DNA序列)。在这种情况下，只有对角线得分是重要的，远离对角线的条目不会对最终距离做出贡献。我们如何避免计算非对角线条目？

PS:忽略边界情况(即当x

Answer 1

在不了解更多具体问题的情况下，一般方法是使用top-down dynamic programming algorithm并对中间结果执行memoize。这样，您将只计算实际使用的值(同时保存结果以避免重复计算)。