Java中的路径数(BackTracking)

Question

插图

你正在测试一辆新的无人驾驶汽车，它位于n×n网格的西南角(左下角)。这辆车应该开到对面，东北(右上)，网格的一角.给定n，网格轴的大小，编写一个函数numOfPathsToDest，返回无人驾驶汽车可能走的路径数。为了方便起见，让我们将网格中的每个正方形表示为对(i，j)。对中的第一个坐标表示东西轴，第二个坐标表示南北轴。汽车的初始状态是(0,0)，目的地是(n-1，n-1).汽车必须遵守以下两条规则:它不能越过对角线边界。换句话说，在每一步中，位置(i，j)都需要保持i >= j。请参见上图中的n= 5。在每一步中，它可能向北一个正方形(向上)，或一个正东(右)，但不是两者兼而有之。如果汽车是在(3,1)，它可以去(3,2)或(4,1)。

示例

input:  n = 4

output: 5 # since there are five possibilities:
          # “EEENNN”, “EENENN”, “ENEENN”, “ENENEN”, “EENNEN”,
          # where the 'E' character stands for moving one step
          # East, and the 'N' character stands for moving one step
          # North (so, for instance, the path sequence “EEENNN”
          # stands for the following steps that the car took:
          # East, East, East, North, North, North)

我的方法：

import java.io.*;
import java.util.*;

class Solution {

  static int numOfPathsToDest(int n) {
    // your code goes here
    //n = 2
    int startX = 0;
    int startY = 0;


    int numPoss = numPaths(startX,startY,n);


    return numPoss;


  }

  static private int numPaths(int startX, int startY, int n )
  {
    int destX = n - 1;
    int destY = n - 1;
    int numPoss = 0;

    //Base case
    if((startX == destX) && (startY == destY ))
      numPoss++;

    //Recursive condition
    else 
      {
        if( (startX >= startY) && (startX < n) && ( startY < n ))
        {
          //East 
          numPoss += numPaths(startX+1, startY,n);

          //North
           numPoss +=  numPaths(startX,startY + 1, n);
        } 

        //Time complexity: O(2^n) -> O(n^2) in memoization
       //Space complexity: O(n^2)
      //Bottom up approach: O(n) space complexity
      //Time complexity: O(n)
      }

    return numPoss;
  }

  public static void main(String[] args) {
    System.out.println(numOfPathsToDest(2));
  }

}

//n = 4
//#squares = 4 + 3 + 2 + 1

//#squares = n + n-1 + n-2 + ... 1 = n(n + 1)/2

//square 0 - eastx 4/ n - 1 

//square (1,0): up - 1, east -  3/(n - 1)

//square (2,0): up - 2, east: 2/(n - 2)

//east + north : n 
//

关于守则，我有以下问题：

1. 在空间和时间复杂度方面，我还能进一步改进代码吗？
2. 有什么更聪明的方法来解决这个问题吗？
3. 我的代码是否违反了任何编码约定？
4. 还有其他方法可以进一步优化代码吗？

参考文献

Answer 1

我有一种感觉，有一种直接的方法来计算这个数值，但我并不是真的对所有的数学，你可以查它。我将讨论您的代码如下：

• 你真的应该删除所有多余的空白，它妨碍了可读性。
• 在Java中，打开大括号并不是在新的行上。
• private先于static。
• 不要将递归函数的结果保存在变量中，您可以立即返回。
• 问题是您从(0, 0)迁移到(n,n)。如果您以相反的方式建模您的代码，您可以简化它很多。例如，不需要将n传递给递归函数，因为您可以简单地与0进行比较。
• 尝试始终使用大括号，即使块中只有一行，例如递归函数中的if部件。它有助于防止由于格式化而引起的未被注意到的错误，并有助于在以后轻松地修改它。
• 在else块中，如果预先检查0，则不需要检查x和y是否有效。
• 在递归函数中，如果初始if成功，结果将始终为1。因此您可以立即返回，它使其更易读。在我看来，早点回来是件好事。然后，可以将该变量放入else中，从而缩小范围。
• 你提到回忆录，但你似乎并没有使用它。如果以这个例子为例，以及在那里所采用的路径：“EEENNN”“EEN\ENN”“EEN\NEN”“ENE\NEN”“ENE\ENN”

请注意，EEN会将您带到与ENE相同的位置。您可以看到，其中每个部分也共享相同的第二部分。这是重复，我们可以用它来加速算法。

如果您仔细考虑一下，通常有多种方法可以到达某个点(x,y)。如果您认为这是起点，那么无论您如何到达目的地，到达目的地的可能路径显然都是相同的。所以，您可以做的是为一个计算的位置创建一个查找表，所以您只计算每个位置一次。这将给你一个极端的加速，我认为，在大量可能的路径的问题上。即使n的值很小，您也会很快得到它。