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?
1 public class Solution{ 2 public int uniquePaths(int m, int n){ 3 if(m < 0 || n < 0 ){ 4 return 0; 5 } 6 if(m == 0 || n == 0){ 7 return 1; 8 } 9 int[][] matrix = new int[m][n]; 10 for(int i = 0 ; i < n; i++){ 11 matrix[0][i] = 1; 12 } 13 for(int j = 0; j < m; j++){ 14 matrix[j][0] = 1; 15 } 16 17 for(int i =1; i < m ; i++){ 18 for(int j = 1; j < n; j++){ 19 matrix[i][j] = matrix[i-1][j] + matrix[i][j-1]; 20 } 21 } 22 return matrix[m-1][n-1]; 23 } 24 }
要到达一个点，就是要从左边或者上边到达，所以，用动态规划存到达每个点的情况。
原文：http://www.cnblogs.com/hewx/p/4532455.html