計算從左上角到右下角任意方向移動的次數

Question

我在面試時遇到了一個問題，這是我發現的一個類似問題，所以我想到這裏問。問題是

有一個機器人位於（1,1）在一個N×N的網格中，機器人可以在任何方向上左右上下移動。另外我得到了一個整數k，它表示路徑中的最大步長。我必須計算以k或更小的步數從（1,1）移動到（N，N）的可能方法的數量。

我知道如何解決這個問題的簡化版本，只有右下方向移動的問題。這可以通過動態編程來解決。我嘗試在這裏應用相同的技術，但我不認爲它可以使用二維矩陣求解，我嘗試了一種類似的方法，從左邊或上邊或右邊計數可能數量的方法，並向下求和，但問題是我不知道應該從哪個方向添加多少個方向。所以我進入循環。我可以使用遞歸來解決這個問題，我可以在（N，N，k）上調用up，left和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

更新：該算法是不正確。看到評論和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 *日誌N）^ 2）溶液，其方式更爲複雜。通過外部for循環的每次迭代不過是與固定內核的卷積。因此，我們可以將內核與自身進行卷積，以獲得將多次迭代融合爲一個的更大內核，並使用FFT計算卷積。

Answer 3

基本上uniquepaths（row，column）= 0 if row> N ||列> N 1 if row == N & & column == N uniquepaths（row + 1，column）+ uniquePaths（row，column + 1） 即，解具有最優子結構和重疊子問題。所以，它可以使用動態編程來解決。下面是記憶的它（懶/點播）版本（相關基本上返回路徑，以及：Algorithm for finding 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)); 
       } 
      } 
     }