0

这是我在一个网站上遇到的动态编程问题。我用下面提到的算法解决了这个问题。虽然我得到的答案是正确的，但评估表明超过了时间限制。

问题是，在 N*N 棋盘上，棋子位于 (xp,yp) 位置。当且仅当 abs(xd-xp)+abs(yd-yp) < = S. 棋子必须走 M 步。这个问题给出了 N,S,M 和 (xp,yp)，我必须找出这块棋子可以使 M 在这个板上移动多少种方式。

我的解决方案如下。

Matrix m0 is initialized with all 0s except with 1 in the location (xp,yp)

Make a N*N matrix m1 for one move from an initialized matrix m0

Make a N*N matrix m2 for two moves from matrix m1

... carry on till m moves and the sum of elements of the final matrix mm 
gives me the number of ways the piece can make M moves on the N*N board 
with given distance constraint S.

我计算矩阵的伪代码如下

for each element (e) in matrix m, 

consider the elements (es) in S*S (S is the distance constraint 
given in the problem) box surrounding the elements.

If (abs(es.x-e.x) + abs(es.y-e.y)) <= S, 
then m[e.x][e.y] = m[e.x][e.y] + m[es.x][es.y]. 

(adding the # of ways that es can be reached with number of ways that e can be reached 
 so that position of e in the matrix contains # of ways that e can be reached from es)

In the S*S box, I considered all  elements except the current element e.

根据我的理解，上述解决方案是 (N^2)*(S^2) 并且运行缓慢，尽管它给出了正确的答案。请提出一个在 N^2 时间内实施的想法。由于它涉及 2D 板，我认为它不能在 O(N) 时间内完成，但我可能错了。

4

1 回答 1

0

这类问题的关键是通过使用滑动窗口来重用部分结果。

例如，假设您知道数组 X 的元素 1 到 1000 的总和是 1234，并且想知道元素 2 到 1001 的总和。快速的方法是计算 1234+X[1001]-X[1]。

在这个问题中，您对绝对值的约束意味着您正在尝试将所有值添加到菱形中。

如果我们现在将窗口沿对角线滑动一步，我们可以通过将左下角的值相加并去掉左上角的值来计算新的总和：

..A..    ..-..   .....
.AAA.    .--A.   ...B.
..A.. -> ..A++ = ..BBB
.....    ...+.   ...B.

在图中，我们添加了标有 + 的值，并删除了标有 - 的值。

这将计算每个新值的操作数量从 O(S^2) 减少到 O(S)。

但是，您可以做得更好，因为您可以使用相同的技巧来预先计算沿每个对角线的值的总和。然后，您可以计算 O(1) 中的每个新值。

于 2013-06-21T09:44:03.437 回答