0062 - Unique Paths

0062 - Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Examples

Input: m = 3, n = 7 Output: 28

Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:

1. Right -> Down -> Down

2. Down -> Down -> Right

3. Down -> Right -> Down

Input: m = 7, n = 3 Output: 28

Input: m = 3, n = 3 Output: 6

Constraints

• 1 <= m, n <= 100

• It's guaranteed that the answer will be less than or equal to 2 * 109

Java Solution (Dynammic Programming)

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] d = new int[m][n];

        for(int[] arr : d) {
          Arrays.fill(arr, 1);
        }
        for(int col = 1; col < m; col++) {
          for(int row = 1; row < n; row++) {
            d[col][row] = d[col - 1][row] + d[col][row - 1];
          }
        }
        return d[m - 1][n - 1];
    }
}