这是我在一个网站上遇到的动态编程问题。我用下面提到的算法解决了这个问题。虽然我得到的答案是正确的,但评估表明超过了时间限制。
问题是,在 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) 时间内完成,但我可能错了。