062.Unique Paths1

Posted on | In

Solution 1: accepted 1ms

Two-dimension DP: For ways to current position, w(current), equals to ways to its top plus ways to its left, w(current) = w(top) + w(left).
Time: O(mn)
Space: O(mn) 

1
2
3
4
5
6
7
8
9
10
11
12
public int uniquePaths(int m, int n) {
      int[][] dp = new int[m][n];
      for(int i = 0; i < m; i++) {
          for(int j = 0; j < n; j++) {
              if(i==0 && j == 0) 
                  dp[i][i] = 1;
              else
                  dp[i][j] = dp[Math.max(0, i-1)][j] + dp[i][Math.max(0, j-1)];
          }
      }
      return dp[m-1][n-1];
}

Solution 2:

One-dimension DP.