Calculating number of moves from top left corner t

问题:

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

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.

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.

回答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.

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

回答2:

Update: This algorithm is incorrect. See the comments and mcdowella's answer. However, the corrected algorithm does not make a difference to the time complexity.

---

It can be done in O(k * N^2) time, at least. Pseudocode:

# 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]

There might be an O(log k * (N*log N)^2) solution which is way more complex. Each iteration through the outer for loop is nothing but a convolution with a fixed kernel. So we can convolve the kernel with itself to get bigger kernels that fuse multiple iterations into one, and use FFT to compute the convolution.

回答3:

Basically uniquepaths( row, column ) = 0 if row > N || column > N 1 if row ==N && column == N uniquepaths(row+1, column) + uniquePaths(row, column+1) i.e, the solution have optimal substructure and overlapped subproblems. So, it can be solved using Dynamic Programming. Below is memorization (lazy/on demand) version of it (related which basically returns paths as well: Algorithm for finding all paths in a NxN grid) (you may refer to my blog for more details: 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;
        }

where the caller is

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;
        }

Unit Tests

[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));
                }
            }
        }