Two solutions of mine in Java.


  • 0
    L
    1. Recursive[Time Limit Exceeded]
    public int walk(int i, int j, int m, int n){
            if(i == m && j == n)
                return 1;
            if(i > m || j > n)
                return 0;
            return walk(i + 1, j, m, n) + walk(i, j + 1, m, n);
                
        }
        public int uniquePaths(int m, int n) {
            return walk(1, 1, m, n);
        }
    
    1. Dynamic Programming.
      Let paths[i][j] be the unique ways to position(i, j).
      paths[i][j] = paths[i-1][j] + paths[i][j-1].
      Because paths[i][j] depends only on the left state and the up state, we minus space complexity from O(mn) to O(n).
      Complexity: Time O(mn), Space O(n).
    public int uniquePaths(int m, int n) {
        int[] paths = new int[n];
        for(int i = 0; i < m; i++){
            paths[0] = 1;
            for(int j = 1; j < n; j++){
                paths[j] += paths[j - 1];
            }
        }
        return paths[n - 1];
    }
    

Log in to reply
 

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