[Path][DP] Unique Path

1. Example

[
  [start,a,b],
  [c,d,e],
  [f,g,end]
]

Unique path:
[start, a,b,e,end]
[start,c,f,g,end]
[start,q,d,g,end]

2. Implementation
Thought 1 recursive
Q1: how to start ?
A1: start from right or down
Q1: how to make sure unique?
A1: since at every point we only have option to move right or down, so there is no chance to move back to already explored point
Q1: hot to stop?
A1: when you hit the right-bottom corner the point (m-1, n-1), we stop

Thought 2 permutation and combination mathematics
top-left to bottom-right needs m+n steps to travel
Within m+n steps, there must be m step belong to down move and n steps belong to right move.
Take down move or right move first, Use Mathematics, given m+n steps, take m belong to down,
assume m = 3 and n = 7, we can take step 1, 4, 6 as down and  the rest are right

Cn r = n! / (n-r)! *r!
Q1: how to calculate r! ?
A1: r1 = 1x2x3x..r, use factorial
Q1: any fast way to calculate C n r ?
A1: C nr = (r+1)x(r+2)..xn / 1x2x3x..(n-r)

// Time:O(min(m,n)), Space:O(1)
public int uniquePaths(int m, int n)
{

    //Cnr = nx..x(n-r) / 1x2x..xr
    double num = 1;
    double denom = 1;


    // NOTE: already at (0,0) choose m-1 and n-1
    big = (m>n)?m-1:n-1;
    small = (m>n)?n-1:m-1;

    for (int i =1 ; i <= small;i++)
    {
        denom *=i;
        num*= (small + big -1) - i;
    }
    return (int) num/denom;
}

// Time:O(2^n), Space:O(n) Time Exceed Limit
public int uniquePaths(int m, int n)
{
     // validate the input 
     if (m == 0 || n == 0)
     {
         return 0;  
     }
     int[] res = new int[2];
     helper(0,0, m,n,res);
     return res[0];
}

//private void helper (int i, int j,int m, int n, int[] res)
private int helper (int i, int j,int m, int n)

{
     // base case to stop
     if (i == m-1 && j == n-1)
     {
          //res[0]++;
          //return;
           return 1;
     }
     //if (i==m || n = n)
     if (i > m-1 || j > n-1) 
     {
          //return;
          return 0;
     }
     // recursive call (any check condition)
     //if ( i < m-1)
     //  helper(i+1,j,m,n,res);
     //if ( j < n-1)
     //  helper(i, j+1,m,n,res);

     return helper(i+1,j,m,n) + helper(i,j+1,m,n);
}

helper(0,0,..)
  helper(1,0,..)
     helper(2,0,..)
      ..
        helper(m-1,0,..)
        retrun;
        helper(m-1,1,..)
           helper(m-1,2,..)
             ..
               helper(m-1, n-1,..)
               count++
               return
             helper(m-1, n-2,..)
WHEN BACKTRACKING, no way to stop it 
assume m =4 n =4
helper(0,0,..)
   helper(1,0)                                        +        helper(0,1,.)
   helper(2,0)                + helper(1,1)                    h(1,1)+              h(0,2)
   h(3,0)+       h(2,1)         h(2,1)+          h(1,2)        h(2,1)+h(1,2)        h(1,2)+h(0,3)
   h(3,1)+h(2,2) h(3,1)+h(2,2)  h(2,2)+h(1,3)    h(2,2)+h(1,3) 
                 h(3,2)+h(2,3)  
                 h(4,2)+h(3,3)  h(3,3)+h(2,4)
       
 

3. Similar Ones
(M) Unique Path II
(M) Minimum Path Sum
(H)  Dungeon Game
        Path Sum
        Path SumII
        Binary Tree Maximum Path Sum