Why not recursion?


  • 1
    I
    public class Solution 
    {
        static int ans = 0;
        public int uniquePaths(int m, int n) 
        {
            if(m == 0 || n == 0 || (m == 1 && n == 1))
                return ans;
            else if(m == 1 || n == 1)
                return 1;
            ans = (uniquePaths(m - 1, n) + uniquePaths(m, n - 1));
            return ans;
        }
    }
    

    I tried to solve the problem with recursion. but always got an Time Limit Exceeded Error. The problem doesnt have time limit constrains. Plus I ran the code above locally, it passed. Any suggestions?


  • 0
    X

    You can use DP to memorize previous results. As there are a lot of repeated computations.


  • 0
    I

    I understand there are better answers, but why this is not even acceptable.


  • 4
    M

    Every problem on this site has time constraints. It is just that not every problem will tell you them in the description. The goal for the judge is to make it such that the only thing that gets accepted on the site is the fastest, most efficient solution. In theory, this site is meant to help people prepare for interviews ("Have you been asked this question in an interview?") and when at an interview, giving a solution that solves the problem slowly when there is a faster way is better than not providing a solution at all, but not the goal. As you have the time to work on the problems here, restricting the problems to only the fastest means that in an actual interview, you know the faster solutions, not just a solution.

    TLE is returned when there is an infinite loop, yes, but it is also returned when there is a faster way to solve the problem. By redoing all the calculations, you make it so the algorithm can take hundreds or thousands of times longer than needed.

    A grid can be viewed as two grids sharing a corner, where all the paths passing through that corner must only exist in the two grids. If a path leaves the first grid, it is too far right or too far down to pass through the cell. Therefore, for cell[a,b], the number of unique paths passing through it are equal to the number of unique paths in an axb grid. However from that cell, there are paths leading from it to the lower left corner, forming a second grid. Too far up or left, and it could not have come from that cell. This second grid is (m-a)x(n-b). If you have 100 paths from top left to the cell(the solution for the axb grid), that cell's unique paths(the solution for the (m-a)x(n-b) grid) will be fully recalculated 100 times, when you could just remember it and calculate it once.


  • 0
    I

    Thanks very much for the answer. I see that it will be much better to do it in another way around.


  • -8
    W

    It is the easiest question in Leetcode. You only know there are (m-1) right steps and (n-1) down steps. All possible route number is the combination number from (n+m-2) to take n-1.

    Factorial function will be called (you can write it)

    class Solution:
        # @return an integer
        def uniquePaths(self, m, n):
            if m==1 or n==1:
                return 1
            else:
                return self.fact(n+m-2)/self.fact(m-1)/self.fact(n-1)
                
        def fact(self,k):
            pdt=1
            for i in range(1,k+1):
                pdt*=i
            return pdt

Log in to reply
 

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