I got Time Limit Exceeded and Why???? Help me with my JAVA Solution


  • 0
    S
    public class Solution {
    
    
    public int uniquePaths(int m, int n) {
         if(m == 1 || n == 1 ){
            return 1;
        }
        return uniquePaths2(m,n)+1;
    }
    
    
      public static int uniquePaths2(int m, int n) {
        int path;
        if(m == 1) {
            return 0;
        }
        
        if(n == 1){
            return 0;
        }
       
            return uniquePaths2(m-1, n) + uniquePaths2(m , n-1)+1; 
        
     
    }}
    

    what is the difference with

     public int getPath2(int m, int n) {
        map = new int[m][n];
        return unique(m - 1, n - 1);
    }
    private int unique(int m, int n) {
        if (m == 0 || n == 0) return 1;
        if (map[m][n] != 0) return map[m][n];
    
        int s = unique(m, n - 1) + unique(m-1, n);
        map[m][n] = s;
        return s;
    }
    

    I suck at the time stuff. Please help me.


  • 1
    C

    First version is a recursive solution, so time Limit Exceed is very likely happened. Try to use DP algorithm as you write in second version. The many different in these two answer is that second one save all the previous value in the array(map), so it can directly get previous value from array but not calculate again, that's why it will save much time than the first version.

    Actually this is also the difference between recursion and dynamic programming.


Log in to reply
 

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