计算在任何方向的移动，从左上角到右下角用移动号码 [英] Calculating number of moves from top left corner to bottom right with move in any direction

问题描述

我已经要求我在接受采访时的一个问题，这是一个类似的问题，我发现，所以我想在这里问的。问题是

I have a problem asked to me in an interview, this is a similar problem I found so I thought of asking here. The problem is

有位于（1,1）的机器人在一个NXN格，机器人可以在左，右，向上和向下的任何方向移动。此外，我已获得的整数k，这表示在路径上的最大的步骤。我不得不计算可能的方式从（1,1）移动到（N，N-）在k或更少的步数。

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.

我知道如何解决这个问题的简化版本，一个与移动可能只向右和向下的方向。这可以解决与动态规划。我试着在这里采用相同的技术，但我不认为它可以使用2维矩阵来解决，我尝试了类似的方法计算，从左侧或向上或向右，总结在上下方向的方式尽可能多的，但问题是我不知道从上下方向的方式应该也可以加号。所以，我走在一个循环。我可以用递归来解决这个问题，我可以递归的（N，N，K）呼吁上，左和k-1，总结起来，但我想这也是不正确的，如果它可能是正确的是有指数的复杂性。我发现类似这样的问题，所以我想知道什么是解决问题的这些类型的一个完美的方法。

I know how to solve simplified version of this problem, the one with moves possible in only right and down direction. That can be solved with Dynamic Programming. I tried applying the same technique here but I don't think it could be solved using 2-dimensional matrix, I tried a similar approach counting possible number of ways from left or up or right and summing up in down direction, but the problem is I don't know number of ways from down direction which should also be added. So I go in a loop. I was able to solve this problem using recursion, I could recurse on (N,N,k) call for up, left and k-1, sum them up but I think this is also not correct, and if it could be correct it has exponential complexity. I found problems similar to this so I wanted to know what would be a perfect approach for solving these types of problems.

推荐答案

假设你有一个N×N的矩阵，其中每一个单元给你的方法可以从（1,1）移动号码（I，J）的k个步骤（某些条目将是零）。现在，您可以创建一个N×N的矩阵，其中每一个单元给你的方法可以从（1,1）移至（I，J）的数量完全相同K + 1步 - 与全零矩阵开始，然后添加在previous基质的细胞（I，J）的细胞第（i + 1，j）的（I，J + 1），...等等。

Suppose you have an NxN matrix, where each cell gives you the number of ways to move from (1,1) to (i,j) in exactly k steps (some entries will be zero). You can now create an NxN matrix, where each cell gives you the number of ways to move from (1,1) to (i,j) in exactly k+1 steps - start off with the all-zero matrix, and then add in cell (i,j) of the previous matrix to cells (i+1, j), (i, j+1),... and so on.

在每个k个矩阵的（N，N）进入给你的方法可以从（1,1）移至（I，J）在完全相同k步数 - 所有你现在要做的就是将它们添加一起。

The (N,N) entry in each of the k matrices gives you the number of ways to move from (1,1) to (i,j) in exactly k steps - all you have to do now is add them all together.

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

这篇关于计算在任何方向的移动，从左上角到右下角用移动号码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！