Pramp – Number of Paths

Question

You’re testing a new driverless car that is located at the Southwest (bottom-left) corner of an n×n grid. The car is supposed to get to the opposite, Northeast (top-right), corner of the grid. Given n, the size of the grid’s axes, write a function numOfPathsToDest that returns the number of the possible paths the driverless car can take.

For convenience, let’s represent every square in the grid as a pair (i,j). The first coordinate in the pair denotes the east-to-west axis, and the second coordinate denotes the south-to-north axis. The initial state of the car is (0,0), and the destination is (n-1,n-1).

The car must abide by the following two rules: it cannot cross the diagonal border. In other words, in every step the position (i,j) needs to maintain i >= j. In every step, it may go one square North (up), or one square East (right), but not both. E.g. if the car is at (3,1), it may go to (3,2) or (4,1).

Explain the correctness of your function, and analyze its time and space complexities.

Example

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

Constraints

• [time limit] 5000ms
• [input] integer n
  • 1 ≤ n ≤ 100
• [output] integer

Solutions

Brute Force

Time Complexity: O(2^(n – 1))
Space Complexity: O(2^(n – 1))

備註：第一步一定是E

DFS Solution

Result: Out of time limit

Time Complexity: O(n!)
Space Complexity: O(1)

備註：
第一步一定是E， n 個 N 跟剩餘的 n-1 個 E 的排列組合
所以時間複雜度是 O((2n – 1)! / (n!(n – 1)!))

def num_of_paths_to_dest_DSF(n):
  if n < 3:
    return 1
  goal = n - 1
  # Num_of_E, Num_of_N
  stack = [[1, 0]]
  paths_n = 0
  while stack:
    E, N = stack.pop()
    if E + 1 <= goal:
      if E + 1 == goal and N == goal:
        paths_n += 1
      else:
        stack.append([E + 1, N])
    if N + 1 <= min(goal, E):
      if N + 1 == goal and E == goal:
        paths_n += 1
      else:
        stack.append([E, N + 1])
  return paths_n

DF Solution (Recursion + memory)

def num_of_paths_to_dest_DP(n):
  if n < 3:
    return 1
  
  return get_paths(n - 1, n - 1)
  
def get_paths(x, y):
  if x < y or x < 0 or y < 0:
    return 0
  if x == 1 and y == 0:
    return 1
  
  if (x, y) in dp:
    return dp[(x, y)]
  
  paths = get_paths(x - 1, y) + get_paths(x, y - 1)
  dp[(x, y)] = paths
  
  return paths

Last Updated on 2023/08/16 by A1go