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?

Unique Paths - 图1

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Solution:

  1. public class Solution {
  2.   public int uniquePaths(int m, int n) {
  3.     int[][] dp = new int[m][n];
  5.     // first row
  6.     for (int j = 0; j < n; j++) {
  7.       dp[0][j] = 1;
  8.     }
  10.     // first col
  11.     for (int i = 0; i < m; i++) {
  12.       dp[i][0] = 1;
  13.     }
  15.     // others
  16.     for (int i = 1; i < m; i++) {
  17.       for (int j = 1; j < n; j++) {
  18.         dp[i][j] = dp[i-1][j] + dp[i][j-1];
  19.       }
  20.     }
  22.     return dp[m-1][n-1];
  23.   }
  24. }