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

Question

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

在N

X N网格的(1,1(处有一个机器人，机器人可以向左，右，向上和向下的任何方向移动。我还得到了一个整数 k，它表示路径中的最大步长。我必须计算以 k 步或更少的步长从 (1,1( 移动到 (N，N( 的可能方法的数量。

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

Answer 1

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

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

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).

Answer 2

更新：此算法不正确。请参阅评论和麦克道拉的答案。但是，校正后的算法对时间复杂度没有影响。

---

它至少可以在 O(k * N^2( 时间内完成。伪代码：

# grid[i,j] contains the number of ways we can get to i,j in at most n steps,
# where n is initially 0
grid := N by N array of 0s
grid[1,1] := 1
for n from 1 to k:
  old := grid
  for each cell i,j in grid:
    # cells outside the grid considered 0 here
    grid[i,j] := old[i,j] + old[i-1,j] + old[i+1,j] + old[i,j-1] + old[i,j+1]
return grid[N,N]

可能有一个 O(log k * (N*log N(^2( 解决方案，它要复杂得多。通过外部for循环的每次迭代只不过是具有固定内核的卷积。因此，我们可以将内核与自身进行卷积，以获得更大的内核，将多个迭代融合为一个，并使用FFT来计算卷积。

Answer 3

基本上唯一路径( 行，列 ( = 0 如果行> N || 列> N 1 如果行 ==N &&列 == N 唯一路径(行+1，列(+ 唯一路径(行，列+1(即，解决方案具有最优子结构和重叠子问题。因此，可以使用动态规划来解决。下面是它的记忆(懒惰/按需(版本(相关，基本上也返回路径：在NxN网格中查找所有路径的算法((您可以参考我的博客以获取更多详细信息：http://codingworkout.blogspot.com/2014/08/robot-in-grid-unique-paths.html(

private int GetUniquePaths_DP_Memoization_Lazy(int?[][] DP_Memoization_Lazy_Cache, int row, 
            int column)
        {
            int N = DP_Memoization_Lazy_Cache.Length - 1;
            if (row > N)
            {
                return 0;
            }
            if (column > N)
            {
                return 0;
            }
            if(DP_Memoization_Lazy_Cache[row][column] != null)
            {
                return DP_Memoization_Lazy_Cache[row][column].Value;
            }
            if((row == N) && (column == N))
            {
                DP_Memoization_Lazy_Cache[N][N] = 1;
                return 1;
            }
            int pathsWhenMovedDown = this.GetUniquePaths_DP_Memoization_Lazy(DP_Memoization_Lazy_Cache,
                row + 1, column);
            int pathsWhenMovedRight = this.GetUniquePaths_DP_Memoization_Lazy(DP_Memoization_Lazy_Cache,
                row, column + 1);
            DP_Memoization_Lazy_Cache[row][column] = pathsWhenMovedDown + pathsWhenMovedRight;
            return DP_Memoization_Lazy_Cache[row][column].Value;
        }

调用方所在的位置

int GetUniquePaths_DP_Memoization_Lazy(int N)
        {
            int?[][] DP_Memoization_Lazy_Cache = new int?[N + 1][];
            for(int i =0;i<=N;i++)
            {
                DP_Memoization_Lazy_Cache[i] = new int?[N + 1];
                for(int j=0;j<=N;j++)
                {
                    DP_Memoization_Lazy_Cache[i][j] = null;
                }
            }
            this.GetUniquePaths_DP_Memoization_Lazy(DP_Memoization_Lazy_Cache, row: 1, column: 1);
            return DP_Memoization_Lazy_Cache[1][1].Value;
        }

单元测试

[TestCategory(Constants.DynamicProgramming)]
        public void RobotInGridTests()
        {
            int p = this.GetNumberOfUniquePaths(3);
            Assert.AreEqual(p, 6);
            int p1 = this.GetUniquePaths_DP_Memoization_Lazy(3);
            Assert.AreEqual(p, p1);
            var p2 = this.GetUniquePaths(3);
            Assert.AreEqual(p1, p2.Length);
            foreach (var path in p2)
            {
                Debug.WriteLine("===================================================================");
                foreach (Tuple<int, int> t in path)
                {
                    Debug.Write(string.Format("({0}, {1}), ", t.Item1, t.Item2));
                }
            }
            p = this.GetNumberOfUniquePaths(4);
            Assert.AreEqual(p, 20);
            p1 = this.GetUniquePaths_DP_Memoization_Lazy(4);
            Assert.AreEqual(p, p1);
            p2 = this.GetUniquePaths(4);
            Assert.AreEqual(p1, p2.Length);
            foreach (var path in p2)
            {
                Debug.WriteLine("===================================================================");
                foreach (Tuple<int, int> t in path)
                {
                    Debug.Write(string.Format("({0}, {1}), ", t.Item1, t.Item2));
                }
            }
        }

Answer 4

将有无限的方法。这是因为您可以形成无限的位置循环，从而形成无限的可能性。例如：- 您可以从 (0,0( 移动到 (0,1(，然后移动到 (1,1(，然后是 (1,0(，然后再回到 (0,0(。这形成了一个位置循环，因此任何人都可以绕这些类型的循环，并具有无限的可能性。