Solve Unique Paths with linear algorithm?


  • 9
    L
    1. The formula : C(n + m - 2, n - 1)
      Overflow is the problem. Would you do it with this formula? Thanks.

    2. Using DP Time Complexity is O(m * n) Space Complexity is O(min(m, n))

       class Solution {
       public:
           int uniquePaths(int m, int n) {
               // IMPORTANT: Please reset any member data you declared, as
               // the same Solution instance will be reused for each test case.
               if((m <= 0) || (n <= 0)) return 0;
               if((1 == m) || (1 == n)) return 1;
               int map[n + 1];
               memset(map, 0, sizeof(map));
               for(int i = 1; i <= n; i ++) map[i] = 1;
               for(int i = 2; i <= m; i ++) {
                   for(int j = 2; j <= n; j ++) {
                       map[j] += map[j - 1];
                   }
               }
               return map[n];
           }
       };

  • 0
    L
    This post is deleted!

  • 16
    C

    I have no idea what the formula means. I think you can use some math formula to solve this problem.
    Here is my solution.

    class Solution {
    public:
        int uniquePaths(int m, int n) {
            vector<int> map(m+1, 0);
            map[1]=1;
            for(int i=0; i<n; i++){
                for(int j=1; j<=m; j++)
                    map[j] = map[j-1]+map[j];
            }
            return map[m];
        }
    }
    

    ;


  • -1
    N
    This post is deleted!

  • 17
    P

    Here is the implementation of C(m,n) without overflowing the answer.

    int gcd(int a, int b) {
        while(b) {
            int c = a%b;
            a = b;
            b = c;
        }
        return a;
    }
    
    int C(int m, int n) {
        if(m - n < n) {
            n = m - n;
        }
        int result = 1;
        for(int i = 1; i <= n; i++) {
            int mult = m;
            int divi = i;
            int g = gcd(mult,divi);
            mult /= g;
            divi /= g;
            result /= divi;
            result *= mult;
            m--;
        }
        return result;
    }
    

  • 0
    W

    assume it is a area of n*m, width is n
    n+m-2 means the length of one path
    n-1 means you have to choose (n-1) times to move horizontally
    Hence the total possible path number is Combination(n+m-2, n-1)


  • 0
    W

    m=3, n = 4 will not return correct answer


  • 0
    P

    That is because m should not be smaller than n


  • 0
    W

    I see :-)
    "C" is short for "Combination" not the original function uniquePaths(m, n)
    Elegant gcd !!!


  • 0
    P

    Yep. C(m, n) will return the number of different ways you can choose n items out of m.


  • 6
    A

    Divide as you go along to delay overflow

    public class Solution {
        public int uniquePaths(int m, int n) {
            return combination(m + n - 2, n - 1);
        }
        
        private int combination(int m, int n){
            if(n > m / 2)   return combination(m, m - n);
            else{
                double result = 1;
                for(int i = 1; i <= n; i++){
                    result *= m - n + i;
                    result /= i;
                }
                return (int)result;
            }
        }
    
    }

  • 0
    G
    This post is deleted!

  • 0
    D

    Your solution worked:), nice use of setting the result be double type.


  • 0
    B

    actually you can just set result as long


  • 0
    R

    You perform one passage more with a map n + 1 because you fill your map with 1 0 0 0 ... at the beginning.
    You can cut first step by filling it with 1 1 1 1 1.

    {
    int uniquePaths(int m, int n) {

        // Reduces the problem to m <= n, because internal loop is faster.
        if (m > n) swap(m, n);
        if (m <= 1) return m; // Corner cases, one border is 0 or 1.
        
        // Uses a map to memoize previous results:
        vector<int> map(n, 1); // The map is filled of 1, so that first step is already done.
        
        // For every horizontal step...
        for (int i = 1; i < m; ++i) {
            
            // For every vertical step...
            for (int j = 1; j < n; ++j) {
                
                map[j] += map[j - 1];
            }
        }
        
        // The last element contains our solution.
        return map[n - 1];
    }
    

    }
    }


  • 0
    L

    C(198, 99) = -2138017796
    It is still overflow


  • 0
    P

    Then use long long


  • 0
    L

    result /= divi; // how to prove result can be divided by divi?
    result *= mult;


  • 0
    P

    Otherwise result will not be an integer.


  • 0
    L

    Hi porker2008,

    Your code is right.

    For example.
    s1 = m * (m - 1) * (m - 2) * .... * (m - n + 1)
    s2 = 1 * 2 * 3 * 4 * .... n

    we can prove b = 1 * 2 * 3 * 4 can be divided by m * (m -1) * (m - 2) * (m - 3).


Log in to reply
 

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