algorithm - 计算从左上角到右下角向任何方向移动的移动次数

Question

我有一个问题在面试中被问到，这是我发现的一个类似的问题所以我想在这里问。问题是

There is a robot situated at (1,1) in a N X N grid, the robot can move in any direction left, right ,up and down. Also I have been given an integer k, which denotes the maximum steps in the path. I had to calculate the number of possible ways to move from (1,1) to (N,N) in k or less steps.

我知道如何解决这个问题的简化版本，一个只能在右下方向移动的问题。这可以用动态规划来解决。我尝试在这里应用相同的技术，但我不认为它可以使用二维矩阵来解决，我尝试了一种类似的方法，从左或上或右计算可能的方式数量并在向下方向求和，但问题是我不知道还应该添加的向下方向的方法数。所以我进入一个循环。我能够使用递归解决这个问题，我可以递归调用 (N,N,k) 向上、向左和 k-1，将它们求和，但我认为这也不正确，如果它可以正确的话具有指数复杂度。我发现了与此类似的问题，所以我想知道解决这些类型问题的完美方法是什么。

Answer 1

假设您有一个 NxN 矩阵，其中每个单元格都为您提供从 (1,1) 移动到 (i,j) 的方法数，正好是 k 步(有些条目将为零)。您现在可以创建一个 NxN 矩阵，其中每个单元格都为您提供从 (1,1) 移动到 (i,j) 的方法数，正好是 k+1 步 - 从全零矩阵开始，然后添加在前一个矩阵的单元格 (i,j) 到单元格 (i+1, j), (i, j+1),... 等等。

k 个矩阵中每一个的 (N,N) 条目都为您提供了从 (1,1) 移动到 (i,j) 的方法数，正好是 k 步 - 您现在要做的就是将它们相加一起。

Here is an example for the 2x2 case, where steps outside the 
matrix are not allowed, and (1,1) is at the top left.
In 0 steps, you can only get to the (1,1) cell:

1 0
0 0

There is one path to 1,1. From here you can go down or right,
so there are two different paths of length 1:

0 1
1 0

From the top right path you can go left or down, and from the
bottom left you can go right or up, so both cells have paths
that can be extended in two ways, and end up in the same two
cells. We add two copies of the following, one from each non-zero
cell

1 0
0 1


giving us these totals for paths of length two:

2 0
0 2

There are two choices from each of the non-empty cells again 
so we have much the same as before for paths of length three.

0 4
4 0

Two features of this are easy checks:

1) For each length of path, only two cells are non-zero, 
corresponding to the length of the path being odd or even.

2) The number of paths at each stage is a power of two, because
each path corresponds to a choice at each step as to whether to 
go horizontally or vertically. (This only holds for this simple 
2x2 case).