3

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

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

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

4

4 回答 4

4

假设您有一个 NxN 矩阵，其中每个单元格为您提供了从 (1,1) 移动到 (i,j) 恰好 k 步的方式数（一些条目将为零）。您现在可以创建一个 NxN 矩阵，其中每个单元格都为您提供了从 (1,1) 移动到 (i,j) 的方式数，恰好是 k+1 步 - 从全零矩阵开始，然后添加在前一个矩阵的单元格 (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).
于 2012-05-06T07:11:21.383 回答
1

更新：这个算法不正确。请参阅评论和 mcdowella 的回答。但是，修正后的算法对时间复杂度没有影响。

至少可以在 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 来计算卷积。

于 2012-05-06T07:10:31.613 回答
0

基本上 uniquepaths( row, column ) = 0 if row > N || column > N 1 if row ==N && column == N uniquepaths(row+1, column) + uniquePaths(row, column+1) 即解具有最优子结构和重叠子问题。因此，它可以使用动态规划来解决。下面是它的记忆（惰性/按需）版本（相关的基本上也返回路径：Algorithm for find all paths in a NxN grid）（您可以参考我的博客了解更多详细信息：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));
                }
            }
        }
于 2014-08-02T14:08:47.213 回答
0

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

于 2021-03-15T17:11:59.877 回答