Ruby Solution - Math


  • 0
    I

    As the bot can only turn right/down, and we know how many steps it takes right/down to the finish point. Now we can convert it to a math (probability) problem:

    How many ways to permutate n-1 right object and m-1 down object?

    The answer is (n-1+m-1)! / ( (m-1)! * (n-1)! )

    # Using factorial calculation
    def unique_paths(m, n)
      if m > n
        t = m; m = n; n = t;
      end
    
      return 1 if m == 1
    
      factorial( m-1+n-1) / ( factorial(m-1) * factorial(n-1) )
    end
    
    def factorial(n)
      return 1 if n == 0 or n == 1
    
      n * factorial(n-1)
    end
    

    Suppose sum = n-1+m-1; k = m-1, then it comes to (sum)! / ( k! * (sum-k)! ). We can simplify this formula.

    # Simplified factorial calculation
    def unique_paths(m, n)
      if m > n
        t = m; m = n; n = t;
      end
    
      return 1 if m == 1
    
      sum = m-1+n-1
      k   = m-1
      res = 1
    
      1.upto(k) do |i|
        res = res*(sum-k+i)/i
      end
    
      res
    end
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.